[LeetCode] 39. Combination Sum - 문제풀이

Description

주어진 배열에서 중복이 허용되는 조합의 합이 target이 되는 모든 요소를 반환하는 문제입니다. 요소의 값이 같고 순서가 다른 것은 동일한 조합으로 칩니다.

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

Solution 1. backtracking

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    Arrays.sort(candidates);
    backtracking(result,new ArrayList<>(),candidates,target,0);
    return result;
}

public void backtracking(List<List<Integer>> result, List<Integer> comb, int[] nums, int target, int start){
    //end case
    if(target == 0){
        result.add(new ArrayList<>(comb));
        return;
    }

    for(int i = start; i < nums.length; i++){
        if(nums[i] > target) break;
        comb.add(nums[i]);
        backtracking(result,comb,nums,target - nums[i],0);
        comb.remove(comb.size()-1);
    }

}

백트래킹을 통해 일치하는 값이 있을 때 까지 반복하며 요소를 채워줍니다. 배열을 정렬한 뒤 백트래킹을 하면 요소의값이 타겟보다 커졌을때는 더이상 진행할 필요가 없어지므로 반복되는 재귀 스택수를 줄일 수 있습니다.

Reference

Combination Sum - LeetCode

LeetCode, Algorithm, String, Hash Table, LinkedList, Depth-First Search, Breadth-First Search, Matrix, TwoPoint, Array, Recusion, 릿코드, 알고리즘, 코딩테스트, 코테, 문제풀이

Binary Tree, Recusion, 전위순회, inorder-traversal

중위순회, inorder-traversal, 후위순회, postorder-traversal,