🌕 39. 组合总和

难度: 🌕

问题描述

---

解法 1

class Solution {
    List<List<Integer>> res = new LinkedList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        // 思路：
        // 无重复元素 + 可重复选取
        // 回溯
        LinkedList<Integer> path = new LinkedList<>();
        int len = candidates.length;
        mySol(candidates, target, len, 0, 0, path);
        return res;
    }

    private void mySol(int[] array, int target, int len, int index, int sum, LinkedList<Integer> path) {
        // 递归终止条件判断
        if(sum > target) {
            return;
        }
        if(sum == target) {
            res.add(new LinkedList<>(path));
            return;
        }
        if(index > len) {
            return;
        }
        // index <= len && sum < target
        for(int i = index; i < len; i ++) {
            path.addLast(array[i]);
            mySol(array, target, len, i, sum + array[i], path);
            path.removeLast();
        }
    }
}

---

输出 1

---

解法 2 - 排序 + 剪枝优化

class Solution {
    List<List<Integer>> res = new LinkedList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        // 思路：
        // 无重复元素 + 可重复选取
        // 回溯 + 剪枝
        LinkedList<Integer> path = new LinkedList<>();
        int len = candidates.length;
        Arrays.sort(candidates); // 排序优化
        mySol(candidates, target, len, 0, 0, path);
        return res;
    }

    private void mySol(int[] array, int target, int len, int index, int sum, LinkedList<Integer> path) {
        // 递归终止条件判断
        if(sum > target) {
            return;
        }
        if(sum == target) {
            res.add(new LinkedList<>(path));
            return;
        }
        if(index > len) {
            return;
        }
        // index <= len && sum < target
        for(int i = index; i < len; i ++) {
            if(sum + array[i] > target) {
                return;
            }
            path.addLast(array[i]);
            mySol(array, target, len, i, sum + array[i], path);
            path.removeLast();
        }
    }
}

---

输出 2