回溯&组合问题

前言

“这是我参与8月更文挑战的第16天，活动详情查看：8月更文挑战”

1. NC46 加起来和为目标值的组合(中等)
2. 216. 组合总和 III
3. 39. 组合总和

加起来和为目标值的组合

描述：给出一组候选数 C 和一个目标数 T ，找出候选数中起来和等于 T 的所有组合。

 C 中的每个数字在一个组合中只能使用一次。

注意：

1. 题目中所有的数字（包括目标数  T ）都是正整数\
2. 组合中的数字 ( a_1, a_2, … , a_ka1​,a2​,…,ak​ ) 要按非递减排序 (a1​≤a2​≤…≤ak​ )
3. 结果中不能包含重复的组合
4. 组合之间的排序按照索引从小到大依次比较，小的排在前面，如果索引相同的情况下数值相同，则比较下一个索引。

输入：

[100,10,20,70,60,10,50],80
复制代码

返回值：

[[10,10,60],[10,20,50],[10,70],[20,60]]
复制代码

说明：

给定的候选数集是[100,10,20,70,60,10,50]，目标数是80 

复制代码

思路分析： 与子集问题II 类似， 需要修改的地方是 结束条件

子集问题II

AC 代码：

    ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
    boolean used[];

    public ArrayList<ArrayList<Integer>> combinationSum2(int[] num, int target) {
        if (num == null || num.length == 0) {
            return new ArrayList<>();
        }
        Arrays.sort(num);
        used = new boolean[num.length];
        dfs(num, 0, target, new ArrayList<>());
        return ans;
    }

    void dfs(int[] num, int index, int target, ArrayList<Integer> temp) {
        if (target < 0) {
            return;
        }
        if (target == 0) {
            ans.add(new ArrayList<>(temp));
            return;
        }

        for (int i = index; i < num.length; i++) {
            if (i > 0 && num[i] == num[i - 1] && !used[i - 1]) {
                continue;
            }
            used[i] = true;
            temp.add(num[i]);
            dfs(num, i + 1, target - num[i], temp);
            temp.remove(temp.size() - 1);
            used[i] = false;
        }
    }
复制代码

216. 组合总和 III

找出所有相加之和为 n 的 k 个数的组合 。组合中只允许含有 1 – 9 的正整数，并且每种组合中不存在重复的数字。

说明：

• 所有数字都是正整数。
• 解集不能包含重复的组合。

思路分析：与子集问题I 类似， 需要修改的地方是 结束条件

子集

相当于 给了一个数组里面包含1-9， 修改结束条件的判断， 当临时集合中的元素个数为k 个时，判断是否需要加入到最终的结果中

AC 代码：

    List<List<Integer>> ans = new ArrayList<>();

    public List<List<Integer>> combinationSum3(int k, int n) {
        dfs(k,n,1,new ArrayList<>());
        return ans;
    }

    void dfs(int k, int n, int index, List<Integer> temp) {
        if (temp.size() == k) {
            if (n == 0) {
                ans.add(new ArrayList<>(temp));
            }
            return;
        }

        for (int i = index; i < 10; i++) {
            temp.add(i);
            dfs(k, n - i, i + 1, temp);
            temp.remove(temp.size() - 1);
        }
    }
复制代码

39. 组合总和

给定一个无重复元素的正整数数组 candidates 和一个正整数 target ，找出 candidates 中所有可以使数字和为目标数 target 的唯一组合。

candidates 中的数字可以无限制重复被选取。如果至少一个所选数字数量不同，则两种组合是唯一的。 

对于给定的输入，保证和为 target 的唯一组合数少于 150 个。

思路分析：与子集问题I 类似， 因为candidates 中的数字可以无限制重复被选取， 所以可选择的条件和之前有所不同

AC 代码：

    List<List<Integer>> ans = new ArrayList<>();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        dfs(candidates, target,0, new ArrayList<>());
        return ans;
    }

    void dfs(int[] candidates, int target, int index, List<Integer> temp) {
        if(target < 0){
            return;
        }
        if(target == 0){
            ans.add(new ArrayList<>(temp));
            return;
        }

        for (int i = index; i < candidates.length; i++) {
            int val = candidates[i];
            temp.add(val);
            // 可以无限制重复被选取 ，所以还是从 i开始查找
            dfs(candidates, target - val, i, temp);
            temp.remove(temp.size() - 1);
        }
    }
复制代码