题解 | NC46 #加起来和为目标值的组合#

加起来和为目标值的组合

http://www.nowcoder.com/practice/75e6cd5b85ab41c6a7c43359a74e869a

题目描述

给出一组候选数 c和一个目标数 t，找出候选数中和等于t的所有组合。 c中每个数字在一个组合中只能使用一次。
注意：
1.题目中所有的数字都是正整数。
2.组合中数字（a1,a2...ak）要按非递减排序。
3.结果中不能包含重复的组合。
4.组合之间的排序按照索引从小到大依次比较，小的排在前面，如果索引相同的情况下数值相同，则比较下一个索引。

示例：
侯选数：[10,20,60,10], 目标数：80
组合结果：[[10,10,60], [20,60]]

题目分析

数字的组合是指从候选数中选出若干个数的数字，当它们的和等于目标值时是一个结果，与选择数字的顺序无关。
对于数字的组合情况，每个数字都有选择和不选择的两种情况，总共会有 $2^{n}$ 种情况。可以使用dfs遍历所有的情况，统计选择的数字总和，等于目标值的组合记录下来，示例如图，一共有16种情况：

alt

根据题目的条件，所有的数字都是正整数，可以将候选数按照从小到大的顺序排列，一旦前面累计的sum超过target或者数字本身大小大于target可以直接跳过（后面不会有让sum减小的数），作为剪枝减少递归所需的时间。

解题思路

方法1：dfs递归回溯，使用set记录位置数字是否被访问过

因为数字是不能重复使用的，所以在判断数字是否被访问时，可以使用set来保存访问过的数字，后面在选择时，只要判断set是否包含即可。不过在做了回溯到上一步的时侯，需要取消选择，set也要删除之前选择的数字。
在去除重复的组合时，可以采用和排列去重相同的方式判断：

if(i>0 && num[i]==num[i-1] && !set.contains(i-1))

主要适用于排好序的有重复数字的数组

方法2：dfs递归回溯，改变判断方式

因为组合中的数字不要求数字加入的顺序性，所以dfs中的for循环挑选数字都是从start（选中的数字往后）开始，不需要从数组开头进行选择，而当出现重复数字时，前面的选择其实已经将情况都已经遍历过了，所以后面的数字可以直接跳过，判断简化如下：

if(i>start && num[i]==num[i-1]) continue;

代码实现

方法1：dfs递归回溯，使用set记录位置数字是否被访问过

    ArrayList<ArrayList<Integer>> res = new ArrayList<>();
    HashSet<Integer> set = new HashSet<>();
    public ArrayList<ArrayList<Integer>> combinationSum2(int[] num, int target) {
       //先要排序数组
        Arrays.sort(num);
        // 进行遍历
        dfs(num, target, 0, new ArrayList<Integer>());
        return res;
    }
     
    void dfs(int[] num, int target, int start, ArrayList<Integer> list){
        // 目标值小于0直接返回
        if(target < 0) return;
        // 当目标值为0，即list中的数字和与初始的target值相等
        if(target == 0 && list.size()>0){
            res.add(new ArrayList<Integer>(list));
            return;
        }
        // 不断往后的数字进行选择
        for(int i=start;i<num.length;i++){
            // 按照排列的思路使用set去重
            if(i>0 && num[i]==num[i-1] && !set.contains(i-1)) continue;
            // 后面的数比target大，直接结束
            if(num[i]>target) break;
            // 选择该数
            list.add(num[i]);
            set.add(i);
            dfs(num, target-num[i], i+1, list);
            // 撤销选择
            list.remove(list.size()-1);
            set.remove(i);
        }
    }

时间复杂度： $O (2^{n})$ ，对于数字的组合情况一共有 $2^{n}$ 种，dfs最多会遍历所有的情况，所以时间复杂度为 $O (2^{n})$ ；

空间复杂度： $O (n)$ ，在遍历的过程中需要使用额外的set来存储数字下标，最多存储n个数字，同时还最多需要使用n大小的递归栈空间。

方法2：dfs递归回溯，改变判断方式

    ArrayList<ArrayList<Integer>> res = new ArrayList<>();
    public ArrayList<ArrayList<Integer>> combinationSum2(int[] num, int target) {
        // 1.排序
        Arrays.sort(num);
        dfs(num, target, 0, new ArrayList<Integer>());
        return res;
    }
    
    void dfs(int[] num, int target, int start, ArrayList<Integer> list){
        if(target < 0) return;
        // 获得到目标值
        if(target == 0 && list.size()>0){
            res.add(new ArrayList<Integer>(list));
            return;
        }
        for(int i=start;i<num.length;i++){
            // 去重
            if(i>start && num[i]==num[i-1]) continue;
            if(num[i]>target) break;
            list.add(num[i]);
            // dfs传递下去的数值是 target-num[i]
            dfs(num, target-num[i], i+1, list);
            list.remove(list.size()-1);
        }
    }

时间复杂度： $O (2^{n})$ ，同方法1；