[알고리즘] 부분집합 여부

sample 배열이 base 배열에 포함되는지(부분집합 여부)를 boolean값으로 리턴하는 알고리즘

const isSubsetOf = function (base, sample) {
  base.sort((a, b) => a - b);
  sample.sort((a, b) => a - b);

  const findItemInSortedArr = (item, arr, from) => {
    // 부분집합의 요소 하나와 from값에 0을 넣어 함수 실행
    for (let i = from; i < arr.length; i++) {
      // 0부터 원본 배열의 길이만큼 반복
      if (item === arr[i]) return i;
      // 만약 부분집합의 하나의 요소가 원본 배열에 들어있다면 해당 인덱스를 리턴
      else if (item < arr[i]) return -1;
      // 부분집합의 요소가 원본배열의 요소보다 작으면 -1 리턴
    }
    return -1;
    // 반복문이 끝났는데도 원본 배열에 들어있지 않으면 -1 리턴
  };

  let baseIdx = 0;
  for (let i = 0; i < sample.length; i++) {
    // 부분집합의 개수만큼 반복
    baseIdx = findItemInSortedArr(sample[i], base, baseIdx);
    // 부분집합의 첫 인덱스부터 끝까지의 리턴값을 baseIdx에 할당
    if (baseIdx === -1) return false;
    // 부분집합의 요소가 하나라도 원배열에 포함되어 있지 않으면 false 리턴
  }
  return true;
};