[leetcode][216] Combination Sum III

문제 : leetcode.com/problems/combination-sum-iii/

---

1에서 9까지의 숫자 만 사용할 수 있고 각 조합은 고유 한 숫자 집합이어야한다는 점을 고려하여 숫자 n이되는 k 숫자의 가능한 모든 조합을 찾습니다.

 

숫자 n을 k개의 수의 합으로 만들 때 가능한 조합들을 구하라.

이 때, 수들의 합은 1~9 중 고유한 수들의 조합이다. ex) 가능 : [1,3]. 불가능 : [2,2] -> 2가 겹침

---

백트래킹으로 풀었다.

index 위치에 오름차순으로 숫자(let, i)를 하나씩 대입하면서 n-i, k-1 로 갱신하면서 배열을 만들어나간다. 

k 혹은 n이 음수가 되면 정답이 불가능한 경우다.

n과 k가 모두 0이 되면 정답이 가능한 경우이므로 이때동안 만든 숫자 배열을 정답배열에 추가한다.

이를 숫자 배열을 만들어볼때까지 반복한다.

 

시간복잡도는 대충 구해보면 O(2^min(k,9)). 실제로는 모든 자리 수에 9가지 수가 들어갈 수 있는 것도 아니여서(고유한 숫자 집합을 구해야 하므로) 이보다는 작을것이다.

---

소스코드 : github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/216.%20Combination%20Sum%20III.cpp