LeetCode 39. 组合总和

力扣

1. 从数组中选择一个候选数
2. 求已选候选数的和sum，如果sum==target记录结果
3. 回溯候选数

剪枝：先对数组进行排序，当前候选数大于剩余值结果值，那么后续也找不到一个候选数使得结果等于target，所以不用再进行搜索

public class CombinationSum {

    private int sum = 0;
    private LinkedList list = new LinkedList<>();
    private List> resultList = new ArrayList<>();

    public List> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        dfs(candidates, target, 0);
        return resultList;
    }

    private void dfs(int[] candidates, int target, int start) {
        if (sum > target) {
            return;
        }

        if (sum == target) {
            resultList.add(new ArrayList<>(list));
        }

        for (int i = start; i < candidates.length; i++) {
            // 剪枝：当前值大于剩余值不再搜索
            if (candidates[i] > target - sum) {
                break;
            }

            sum += candidates[i];
            list.add(candidates[i]);

            dfs(candidates, target, i);

            sum -= candidates[i];
            list.removeLast();
        }
    }
}