力扣第39题-组合总和

题目
题目链接

题解

import java.util.*;

class Solution {

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new LinkedList<>();
        Deque<Integer> currComb = new ArrayDeque<>();
        Arrays.sort(candidates);
        backtracking(candidates, 0, currComb, target, res);
        return res;
    }

    private void backtracking(int[] src, int index, Deque<Integer> currComb, int target, List<List<Integer>> res) {
        if (target == 0) {
            List<Integer> copy = new LinkedList<>(currComb);
            res.add(copy);
            return;
        }
        for (int i = index; i < src.length; i++) {
            if (target - src[i] < 0) {
                // 剪枝
                break;
            }
            currComb.addLast(src[i]);
            backtracking(src, i, currComb, target - src[i], res);
            currComb.removeLast();
        }
    }
}