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

题目：加起来和为目标值的组合

描述：给出一组候选数 C和一个目标数 T，找出候选数中起来和等于 T的所有组合。 C中的每个数字在一个组合中只能使用一次。

注意：题目中所有的数字（包括目标数 T）都是正整数，组合中的数字(a1,a2,…,ak)要按非递增排序(a1≤a2≤…≤ak).

结果中不能包含重复的组合，组合之间的排序按照索引从小到大依次比较，小的排在前面，如果索引相同的情况下数值相同，则比较下一个索引。

示例1：输入：[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

解法一：

思路分析：在通读题目的同时，我们可以采用回溯法来解决问题，该题目的实际含义是将集合当中的所有数字相加，当等于target目标数字的时候，返回即可，首先进行排序，然后定义一个最终存储的容器ans，定义一个暂存容器res，将符合条件的元素添加到容器当中，当相加等于target的时候，表示可以返回，将res的值保存后，存入ans容器中即可，其次还要定义一个当前变量cur记录存储的过程值，定义一个指针变量循环执行集合中的元素，主要分为三种情况，分别是：

1、当cur + num[i] > target，表示没有必要继续执行了，后面的所有值均大于target，停止这轮循环，执行下一轮循环。

2、当i > m && num[i-1] == num[i]，题目要求每个数字在一个组合中只能使用一次，当违反条件，则直接执行下一轮循环。

3、进行具体判断。

实例分析：候选数集是[100,10,20,70,60,10,50]，目标数是80

第一轮：

以下就不进行分析了，读者可以自己进行分析运算。

具体C++代码为：

class Solution {
    
private:
    vector ans;
    vector res;//暂存
public:
    void DFS(vector num , int target , int m , int cur){//cur为当前变量，m为循环变量
        if(cur == target){//如果计算的目标数等于的话，直接添加进去
            ans.push_back(res);
            return;
        }
        else{
            for(int i = m ;i < num.size(); i++){ if(cur + num[i] > target)
                    continue;
                if(i > m && num[i-1] == num[i])
                    continue;
                else{
                    res.push_back(num[i]);//加入到暂存容器当中
                    DFS(num, target, i+1, cur + num[i]);//循环进行判断，当发现cur的值相等的时候，直接输出即可
                    res.pop_back();//出一个数继续判断
                }
            }
        }
    }
    
    
    vector combinationSum2(vector&num, int target) {
        sort(num.begin(), num.end());//题目要求按顺序排序，所以先将所有元素排序完整
        DFS(num, target, 0, 0);
        return ans;
    }
};

该算法相当于将所有元素遍历一次后，在遍历的过程中采用回溯的方法进行值的具体判断，故其时间复杂度为O(N^2)，空间复杂度为O(N)。

解法二（与解法一差不多，采用java中的ArrayList对象分析）：

思路分析：首先还是将数组进行排序，方便后序分析，把每一个元素作为起始数字，运用target进行循环判断，与元素后面的数字进行递归判断，最终返回结果值。

具体java代码为：

import java.util.Arrays;
import java.util.ArrayList;
 
class Solution {
    public ArrayList combinationSum2(int[] num, int target) {
        Arrays.sort(num);//排序
        ArrayList res = new ArrayList<>();//最终存储结果的对象
        DFS(num,target,0,res,new ArrayList<>());
        return res;
    }
 
    public void DFS(int[] nums, int target, int index, ArrayList res, ArrayListli){
        if(target < 0){ return ; } if(target == 0){ res.add(new ArrayList<>(li));
            return;
        }
        for(int i = index; i < nums.length; i++){ if(i > index && nums[i-1] == nums[i]){//去除重复
                continue;
            }
            li.add(nums[i]);//把当前元素加入
            DFS(nums,target-nums[i],i+1,res,li);//回溯
            li.remove(li.size()-1);//恢复
        }
    }
}

时间复杂度同上，也为O(N^2)。