69. Combination Sum

Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

The same repeated number may be chosen from candidates unlimited number of times.

Note:

All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.

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

解题思路：
考虑两个条件：

• 组合元素可以重复
• 和为 target
  递归三要素：
• 递归的定义
  找到所有和为 target 的组合，放到 result

• 递归的拆解

• 递归的出口

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> results = new ArrayList<>();
        if (candidates == null){
            return results;
        }
        List<Integer> combination = new ArrayList<>();
        Arrays.sort(candidates);
        recursion(candidates,0,target,combination,results);
        return results;
    }

    // 1. 递归定义
    public void recursion(int[] candidates,
                         int startIndex,
                         int remainTarget,
                         List<Integer> combination,
                         List<List<Integer>> results){
        // 3. 递归出口
        if (remainTarget == 0){
            results.add(new ArrayList<Integer> (combination));
            return;
        }

        // 2. 递归拆解
        for (int i = startIndex; i< candidates.length;i++){
            if (remainTarget < candidates[i]){
                break;
            }

            if (i!=0 && candidates[i] == candidates[i-1]){
                continue;
            }

            combination.add(candidates[i]);
            recursion(candidates,i,remainTarget - candidates[i], combination,results);
            combination.remove(combination.size()-1);
        }
    }
}