377. Combination Sum IV

문제링크: https://leetcode.com/problems/combination-sum-iv/

목표값을 nums 원소의 합으로 나타내는 방법의 경우의 수를 구한다.

Solution

1. Dynamic programming (bottom-up)

모든 경우의 수를 탐색해 구할 수도 있지만 target의 경우의 수는 comb[target - num] 들의 합으로 구할 수 있다. 따라서 target을 아래서부터 계산한다면 피보나치 수열처럼 효과적으로 계산할 수 있다.

Algorithm

• 각 target에 대한 memoization을 할 targets배열을 만든다.
• targets[0]에는 1을 넣고 1부터 targets[i] = targets[i - num[0]] + targets[i - num[1]] + ... + targets[i - num[nums.length - 1]]을 반복한다
• 결과적으로 targets에는 target까지의 결과값이 들어있게 된다.

var combinationSum4 = function(nums, target) {
  // dp
  const targets = new Array(target + 1).fill(0);
  targets[0] = 1;
  for (let i = 1; i < target + 1 ; i++) {
    for (let num of nums) {
      if (i - num >= 0) {
        targets[i] += targets[i - num];
      }
    }
  }
  return targets[target];
};

2. Dynamic programming (top-down)

피보나치 수열의 점화식으로 부터 파생되어 생각했기 때문에 먼저 위의 bottom-up방식을 떠올렸고 연역적으로 이해하기도 쉽다. 하지만 몇몇의 경우의 수에 대해선 1 ~ target의 모든 값을 구할 필요가 없다.

ex) [3,6,9] 12 는 12의 결과를 얻기 위해 1, 2, 4, 5, 7, 8의 결과를 구할 필요가 없다.

이런 부분을 제거하기 위해 필요한 값만 구하는 top-down의 방식을 사용해보기로 했다.

Algorithm

• getComb(tar)함수는 targets 배열에 targets[tar] 값이 없을 경우 실행해 해당 값을 구하고 배열에 넣는다.
• 함수를 재귀적으로 실행해 목표값에 필요한 연산을 한번씩 하면서 결과를 얻는다.

var combinationSum4 = function(nums, target) {
  // dp
  const targets = new Array(target + 1);
  targets[0] = 1;
  
  const getComb = (tar) => {
    let count = 0;
    for (let num of nums) {
      if (tar - num < 0) continue;
      if (targets[tar - num] === undefined) {
        getComb(tar - num);
      }
      count += targets[tar - num];
    }
    targets[tar] = count;
  }
  getComb(target);
  return targets[target];
};

결과를 낸 후 targets배열을 들여다 보면 bottom-up방식은 target까지의 모든 결과를 구했고, top-down방식은 연산에 필요한 부분만 구해 저장해 더욱 효율적임을 알 수 있다.