39. Combination Sum

题目分析

找出一个数组若干数的和等于 target 的所有可行解，每个元素可以重复任意次使用 + 回溯法

代码

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        if(candidates == null || candidates.length == 0) return res;
        List<Integer> combination = new ArrayList<>();
        Arrays.sort(candidates);
        helper(res, candidates, combination, 0, target);
        return res;
    }
    public void helper(List<List<Integer>> res, int[] candidates, List<Integer> combination, int index, int target) {
        // 寻找到了目标解
        if(target == 0) {
            res.add(new ArrayList<Integer>(combination));
            return;
        }
        for(int i = index; i < candidates.length; i++) { 
            if(candidates[i] > target) {
                break;
            }
            
            if(i != index && candidates[i] == candidates[i - 1]) {
                continue;
            }
            
            combination.add(candidates[i]);
            helper(res, candidates, combination, i, target - candidates[i]);
            // helper 执行完了，要么是已经添加了可行解不满足条件，回溯
            combination.remove(combination.size() - 1);
        }
    }
}