[Leetcode] 39. Combination Sum

문제)

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: []

Example 4:

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

Example 5:

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

 

Constraints:

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

풀이)

import java.util.*;
import java.util.stream.Collectors;

public class CombinationSum {
    private void combination(int[] candidates, int target, int curVal, List<Integer> comb, List<List<Integer>> resultList) {
        int candidateSize = candidates.length;
        if(curVal == target) {
            resultList.add(new ArrayList<>(comb.stream().sorted().collect(Collectors.toList())));
            return;
        } else if(curVal > target) {
            return;
        }
        for (int i = 0; i < candidateSize; i++){
            comb.add(candidates[i]);
            combination(candidates, target, curVal+candidates[i], comb, resultList);
            comb.remove(comb.size()-1);
        }
    }
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<Integer> comb = new ArrayList<>();
        List<List<Integer>> resultList = new ArrayList<>();
        combination(candidates, target, 0, comb, resultList);
        return resultList.stream().distinct().collect(Collectors.toList());
    }
}

1. 설명

 - Backtracking 사용. 즉, 재귀를 통해 조건을 만족하는 경우만 목표값을 추적.

 - 재귀를 위해 함수를 하나 만들어서 추적하게 함. (매개변수에는 현재값, 배열, 결과리스트를 추가로 넘김)

 

2. 제출결과

 

3. 시간복잡도

O(n²)

 

4. 개선사항

결과값을 Set으로 받아서 정렬을 하면 좀 더 빨라질 것 같다. 아무래도 distinct와 정렬이 들어간 코드다보니 불필요하게 시간을 더 잡아먹는거같다.

 

5. 새로 알게된 사실

 매개변수 값을 리스트에 추가할 때, resultList.add(new ArrayList<>(comb)) 와 같이 써야한다.

그냥 resultList.add(comb)를 하면, comb의 pointer를 넣어서 빈값이 들어간다. 따라서, new ArrayList<>(comb)로 써서 값을 복사해줘야한다.