[알고리즘] subsetSum (부분집합의 합)

[문제]

자연수의 집합(set)과 자연수(bound)를 입력받아 아래의 조건을 만족하는 가장 큰 수를 리턴해야 합니다.

• 집합의 요소를 최대 한번씩만 더해서 만들어야 한다.
• bound를 넘지 않아야 한다.

[입력]

• 인자 1: set
• 자연수를 요소로 갖는 배열
• 인자 2: bound
• number 타입의 자연수 (bound <= 300)

[주의사항]

조건을 만족하는 조합이 없는 경우, 0을 리턴해야 합니다.

[풀이]

1. 첫번째 풀이
처음엔 조합과 while문을 이용해서 1개~길이만큼의 모든 경우의 수를 구해서 max를 구했다.
하지만 역시나 시간복잡도가 압도적으로 커서 풀이를 변경할 수 밖에 없었다.

<조합(재귀) + 반복문 이용한 풀이>
const subsetSum = function (set, bound) {
    //조합 재귀식
  const combination = (arr, selectNum) => {
    if(selectNum === 1) return arr.map((v) => [v]);
    let results = [];

    arr.forEach((fixed, idx, origin) => {
      const rest = origin.slice(idx+1);
      const combinations = combination(rest, selectNum - 1);
      const attached = combinations.map((each) => [fixed, ...each]);
      results.push(...attached);  
    })
    return results;
  }
  let count = 1;
  let max = 0;
  
  // 길이만큼의 조합을 구한다.
  while(count <= set.length) {
    let results = combination(set, count); // 여기서 재귀식으로 
    results.forEach((each) => { //reduce로 각 조합의 합계를 구함
      const sum = each.reduce((acc, cur) => acc + cur);
      // bound이하거나 sum보다 크면 max로 할당
      if(sum <= bound && sum > max) max = sum; 
    })
    count++;
  };
  return max;
};

2. 두번째 풀이
객체를 활용한 식으로, 객체에 bound보다 작은 값을 넣어주고, 그 값이 들어있는 객체를 forEach로 계속 돌리기에
for문이나 재귀보다 시간복잡도가 덜 걸린다.

const subsetSum = function (set, bound) {
  let max = 0;
  let reachable = {};
// set의 값마다 돌면서
  set.forEach((member) => {
    // reachable 객체만큼 안에서 다시 돌아준다.
    Object.keys(reachable).forEach((r) => {
      //객체는 string타입으로 number로 변환
      const sum = Number(r) + member;
      if(sum <= bound) {
        reachable[sum] = true;
        if(sum > max) {
          max = sum
        }
      } 
    })
    if(member <= bound) {
      reachable[member] = true;
      if(member > max) {
        max = member;
      }
    }
  })
  return max
};