[재귀][leetcode]39.combination sum

알고리즘
재귀, dp

유형
조합

문제

candidates = 서로다른 정수들
target = 타겟 정수
return = 더해서 타겟정수가 나오는 모든 유니크한 candidate 조합.

예제

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

문제풀이

이 문제는 nCr의 n과 r이 정해져있지 않는 조합이다.
보통의 조합이라면
n개의 요소에서 r개를 뽑는 조합이지만,

이런 문제는 어떻게 풀어야하지?
~~우선 기본적인 조합을 구현하는 코드를 써서 수정을 하는 아이디어로 가보기로 했다.
~~

이런 아이디어가 아니었다.
r이 동적으로 들어가고, 요소가 중복으로 들어가기 때문에 조합이라는 개념에도 맞지 않는다.
이름만 combination..

어떻게 풀면 좋을까?

고민을 하다가, 알고달레에서 두가지 방법을 찾게 되었다.

1. 재귀를 활용한다.
   변수

• output : 리턴값
• nums: 현재 조합을 담는 배열

탈출조건

• total > target 일때 return
• total과 tartet이 같을 때, output에 조합을 추가

동작원리

• dfs의 start는 index, total은 nums의 합
• candidates를 순회하면서, total이 target을 초과하거나 같을때까지 재귀.
• 재귀가 끝나면(탈출조건), 현재 조합에서 마지막 요소를 빼서 다음 candidate로 넘어감.
• 즉, 순회하면서 교체하는 원리임.(백트렉킹)

var combinationSum = function(candidates, target) {
    const result = []
    const nums = []
    const dfs = (start,total) => {
        if(total > target) return
        if(target == total) {
            result.push([...nums])
            return
        }
        for(let i=start;i<candidates.length;i++){
            const num = candidates[i];
            nums.push(num);
            dfs(i,num + total)
            nums.pop()
        }
    }
    dfs(0,0)
    return result
};

2. dynamic programming
   우리가 주로 알고있는 dp의 구조를 활용한다.
   근데, 그중에서도 bottom up을 활용한다.
   왜냐하면, 제목에서 알 수 있듯이 조합의 문제이므로
   작은 조합(합)을 통해서 그것보다 더 큰 조합을 구하는 방법이기 때문이다.

그래서 동작원리는 이렇다

• dp를 target+1길이만큼 만든다.
• dp[0]을 [[]]로 초기화
• candidate를 순회하면서, 현재 candidate~target의 구간에서의 num을 index로 만들고
• dp의 현재 num(index) 에서 candidate를 뺀 index에 대한 조합을,
• dp[num]에 조합 배열에 candidate를 추가한 배열을 넣어준다.

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum = function(candidates, target) {
    const dp = [];
    for(let i=0;i<target+1;i++){
        dp[i] = [];
    }
    dp[0] = [[]]
    for(let candidate of candidates){
        for(let num = candidate;num<target+1;num++){
            for(let combination of dp[num - candidate] ){
                dp[num].push([...combination,candidate])
            }
        }
    }
    return dp[target]
};

참고자료
https://www.algodale.com/algorithms/recursion/
https://www.algodale.com/problems/combination-sum/
https://leetcode.com/problems/combination-sum/description/