[Leetcode] 40. Combination Sum II

문제)

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target.

Each number in candidates may only be used once in the combination.

Note: The solution set must not contain duplicate combinations.

 

Example 1:

Input: candidates = [10,1,2,7,6,1,5], target = 8 Output: [ [1,1,6], [1,2,5], [1,7], [2,6] ]

Example 2:

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

 

Constraints:

• 1 <= candidates.length <= 100
• 1 <= candidates[i] <= 50
• 1 <= target <= 30

풀이)

class Solution {
    private void combination(int[] candidates, int target, int curVal, LinkedList<Integer> comb, List<List<Integer>> resultList, int[] mem) {
        int candidateSize = candidates.length;
        if(curVal == target) {
            resultList.add(new ArrayList<>(comb.stream().sorted().collect(Collectors.toList())));
            return;
        }
        for (int i = 0; i < candidateSize; i++){
            if(mem[i] == 1) continue;
            if(curVal+candidates[i] > target) {
                break;
            }
            comb.addLast(candidates[i]);
            mem[i] = 1;
            combination(candidates, target, curVal+candidates[i], comb, resultList, mem);
            mem[i] = 0;
            comb.removeLast();
        }
    }

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        int[] mem = new int[candidates.length];
        LinkedList<Integer> comb = new LinkedList<>();
        List<List<Integer>> resultList = new ArrayList<>();
        int sum = 0;
        for(int i = 0; i < candidates.length; i++){
            sum+=candidates[i];
        }
        if(sum < target) {
            return resultList;
        }
        if(sum == target) {
            List<Integer> list = new ArrayList<Integer>(Arrays.stream(candidates).boxed().collect(Collectors.toList()));
            resultList.add(list);
            return resultList;
        }
        Arrays.sort(candidates);
        combination(candidates, target, 0, comb, resultList, mem);
        return resultList.stream().distinct().collect(Collectors.toList());
    }
}

1. 설명

 - backtracking + memorization 조합으로 풂

 - candidates[]의 모든 값의 합이 target보다 작은경우 바로 리턴하도록 예외처리

 

2. 제출결과

 

3. 시간복잡도

 

4. 의문점

 Collections.sort(candidates)는 왜 안먹힐까..? resultSet.add(new ArrayList<>(comb.stream().sorted().collect(Collectors.toList()))); 해야 제대로 값이 나오는 이유는..?

 

 리스트의 모든 합을 for문 안쓰고 더하는 방법은 없을까?