Combination Sum
LeetCode의 Combination Sum 문제를 함께 풀어보도록 하겠습니다.
문제
중복이 없는 숫자로 이뤄진 candidates 배열과 숫자 target이 주어졌을 때, 숫자 배열로 부터 합이 target이 되는 모든 조합을 찾아라.
같은 숫자가 여러 번 사용할 수 있으며, candidates 배열 내의 숫자와 target은 모두 양의 정수이다.
- Example 1:
Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
[7],
[2,2,3]
]- Example 2:
Input: candidates = [2,3,5], target = 8,
A solution set is:
[
[2,2,2,2],
[2,3,3],
[3,5]
]풀이
문제에서 주어진 첫번째 예제를 따라가보면서 생각해보겠습니다.
candidates = [2, 3, 6, 7], target = 7제일 먼저 2를 선택하면, [2, 3, 6, 7]를 이용해서 5 (= 7 - 2)를 만들어야 합니다.
result = [2]
candidates = [2, 3, 6, 7], target = 5한 숫자를 여러 번 사용할 수 있기 때문에, 다시 2를 선택하면, [2, 3, 6, 7]를 이용해서 3 (= 7 - 2 - 2)를 만들어야 합니다.
result = [2, 2]
candidates = [2, 3, 6, 7], target = 3또 다시 2를 선택하면, [2, 3, 6, 7]를 이용해서 1 (= 7 - 2 - 2 - 2)를 만들어야 합니다.
result = [2, 2, 2]
candidates = [2, 3, 6, 7], target = 1여기서 우리는 [2, 3, 6, 7]를 이용해서 1을 만들기는 불가능하다는 것을 알 수 있습니다.
따라서 2 대신에 3을 선택하면, [2, 3, 6, 7]를 이용해서 0 (= 7 - 2 - 2 - 3)를 만들어야 합니다.
result = [2, 2, 3]
candidates = [2, 3, 6, 7], target = 0이렇게 합이 target가 일치하는 첫번째 조합인 [2, 2, 3]을 얻게 되었습니다!
마지막 단계에서 전에 넣었던 값을 빼고 다음 값을 넣는 소위 백트랙킹(backtracking)이라고 불리는 기법이 사용되었습니다.
또한 매번 새로운 값을 선택할 때 마다, 줄어든 target 값에 대해서 동일한 candidates 배열을 가지고 동일한 로직을 반복하고 있음을 알 수 있습니다.
따라서 이 문제는 백트랙킹과 재귀 알고리즘을 이용해서 어렵지 않게 풀 수 있습니다.
한 가지 주의할 점이 있는데, 첫번째는 조합은 원소의 순서가 중요하지 않다는 것입니다.
예를 들어, [2, 2, 3]과 [2, 3, 2]는 동일한 조합으로 취급됩니다.
이 부분을 간단히 처리할 수 있는 방법은 candidates 배열 내의 숫자를 정렬해놓고 시작하는 것입니다.
Python
candidates를 정렬하기 위해서 리스트의 sort() 매서드를 사용하였습니다.
class Solution:
def combinationSum(self, candidates, target):
candidates.sort()
results = []
nums = []
def helper(target, start):
for idx in range(start, len(candidates)):
num = candidates[idx]
if target == num:
results.append(nums + [num])
elif target > num:
nums.append(num)
helper(target - num, idx)
nums.pop()
helper(target, 0)
return resultsJava
candidates를 정렬하기 위해서 Arrays 클래스의 sort() 정적 메서드를 사용하였습니다.
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> results = new ArrayList<>();
Stack<Integer> nums = new Stack<>();
Arrays.sort(candidates);
helper(candidates, target, results, nums, 0);
return results;
}
private void helper(int[] candidates, int target, List<List<Integer>> results, Stack<Integer> nums, int start) {
if (target == 0) {
results.add(new ArrayList<>(nums));
return;
}
for (int i = start; i < candidates.length; i++) {
int num = candidates[i];
if (target < num) break;
nums.push(num);
helper(candidates, target - num, results, nums, i);
nums.pop();
}
}
}