39. Combination Sum

Combination Sum

Combination Sum - LeetCode

- 문제 내용 : 주어진 숫자로 이루어진 Array로 목표 값을 구성 할 수있는 모든 subsets을 반환하시오

 

-접근 방법

• DP
• Backtracking

나의 첫번째 접근은 DP였다. Candidates[i]의 최고 값이 200이었기 때문에 DP로 충분 하지 않을까 했지만 속도로는 좋지 못했다. 그 이유는 중복을 처리 하는 부분과 Sorting 처리 하는 부분을 사용하는 것 때문에 문제가 된것으로 보인다.

DP 접근은 다음과 같이 했다.

Input: candidates = [2,3,6,7], target = 7

라고 하면 target 의 값을 1 부터 7가지 늘려가는 방법을 사용했다.

여기서 dp의 index를 target이라고 생각 하였다.

예를 들자면 target이 5이고 cadidates[0]이 2일경우 target 5는 

5-2 = 3 임으로 dp[2]의 subsets과 3으로 이루어 지게 된다.

dp[0] = [[]]

dp[1] = null

dp[2] = [[2]] => target이 2일경우 dp[0]과 2로 이루어짐으로 dp[2]는 [[2]] 이다.

dp[3] = [[3]]

dp[4] = [[2,2]] => dp[2] = [[2]]와 2로 이루어진다.

dp[5] = [[2,3],[3,2]] => dp[2]와 3, dp[3]과  2로 이루어진다. 그러나 이루어진 값이 같음으로 [[2,3]]이 된다.

dp[6] = [[2,2,2],[3,3],[6]] => dp[2] + dp[4]로 이루어 지고 6자체의 subsets으로 이루어 진다.

dp[7] = [[2,2,3],[7]] => dp[5]와 2 그리고 7로 이루어 지거나, dp[3] + dp[4]로 이루어 진다. 

var combinationSum = function(candidates, target) {
    let dp = new Array(target + 1);

    dp[0] = [[]];

    candidates.sort((a, b) => a - b);

    for (let i = 1; i <= target; i++) {
        buildCombination(i);
    }

    return dp[target];

    function buildCombination(target){
        let result = new Array();

        for (let i = 0; i < candidates.length && candidates[i] <= target; i++) {
            let remainder = target - candidates[i];
            if (dp[remainder] != null) {
                let preArray = dp[remainder];

                preArray.forEach(value=> result.push([...value,candidates[i]].sort((a,b)=>a-b)));
            }
        }

        result = result.sort().filter((a, idx) => JSON.stringify(result[idx]) !== JSON.stringify(result[idx+1]));
        dp[target] = [...result];
    }
};

시간복잡도를 보자면 1부터 Target까지의 T회를 회전하고 Target 보다 작은 값으로 candidates 순환 한다. Upper Bound를 보았을 때 T * Cadidates Length로 이루어 지고 sort처리로 nlog과 filter처리로 result length 만큼 처리 된다.

 두번째 접근 방법은 Back Tracking이다.

기본 전략은 다음과 같다.

Combination Sum Back Tracking

Cadidates의 갯수로 각 Node를 Leaf까지 내려가면 된다.

여기서 주의 해야 할것은 목표 값보다 이미 넘은 Node는 더이상 내려가지 말고 계산을 멈춘다는 것이다.

상기 그림에서 보면 Sum이 7이 넘어 가는 순간 Leaf로 정의하고 더이상 내려가지 않아도 된다.

var combinationSum = function(candidates, target) {
    let result = new Array();
    dfs(candidates, target, result, new Array());
    return result;

    function dfs(candidates, target, res, out, start = 0){
        if(target < 0) return;
        if(target === 0){
            res.push(out.slice(0));
            return;
        }
        for(let i = start; i < candidates.length; ++i){
            out.push(candidates[i]);
            dfs(candidates, target-candidates[i], res, out, i);
            out.pop();
        }
    };
};

시간 복잡도는 Cadidates의 갯수를 N이라고 하면

N에서 한 Depth를 내려갈 수로 N*N으로 Node가 늘어나게 된다. 즉 Depth의 깊이만큼 N이 제곱 되게 되는데 이는 다음과 같이 나타낼수 있다.

Target / Min value (candidates) 

예를 들자면 최소값이 1이고 목표값이 7이라고 하면 [1,1,1,1,1,1,1] 이렇게 답이 가능하기 때문에 Upper Bound를 기준으로 N^(Target/Min) + 1(root node)이 시간 복잡도가 된다.