[leetcode #39] Combination Sum

Problem

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

It is guaranteed that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

Example 1:

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.

Example 2:

Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]

Example 3:

Input: candidates = [2], target = 1
Output: []

Constraints:

・ 1 <= candidates.length <= 30
・ 1 <= candidates[i] <= 200
・ All elements of candidates are distinct.
・ 1 <= target <= 500

Idea

재미있는 문제인데 풀지 못 했다. 이런 문제를 잘 풀어야 추후 면접 알고리즘도 잘 볼 수 있을텐데 큰 일이다.

candidates라는 배열에 있는 수들을 조합한 합이 target이 되는 경우를 구하면 된다. 1부터 target까지의 수를 dp에 저장하면 풀 수 있을 거라 생각했지만 중복되는 경우가 많아 이 방향이 아닌 걸 깨닫게 되었다.

재귀함수를 이용하면 되는데 답이 될 수 있는 리스트를 가지고 현재 리스트의 합이 target보다 작을 경우 배열의 원소를 하나씩 더하는 방식으로 풀면 된다. 원소를 하나씩 더할 때마다 새로운 리스트를 만들어 데이터가 변경되지 않도록 한다. 재귀함수에서 target이 0이 되면 유효한 조합이 나온 것이므로 정답에 추가하면 된다.

Time Complexity: O(n²)
Space Complexity: O(n)

Solution

class Solution {
    List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        findCombination(candidates, target, 0, new ArrayList<>());

        return res;
    }

    private void findCombination(int[] candidates, int target, int curIndex, List<Integer> curList) {
        if (target == 0) {
            res.add(curList);
        }

        for (int i=curIndex; i < candidates.length; i++) {
            if (target >= candidates[i]) {
                List<Integer> list = new ArrayList(curList);
                list.add(candidates[i]);
                findCombination(candidates, target - candidates[i], i, list);
            }
        }
    }
}

Reference

https://leetcode.com/problems/combination-sum/