一.题目描述
NC46加起来和为目标值的组合
题目链接:
https://www.nowcoder.com/practice/75e6cd5b85ab41c6a7c43359a74e869a?tpId=188&&tqId=38629&rp=1&ru=/activity/oj&qru=/ta/job-code-high-week/question-ranking
给出一组候选数C和一个目标数T，找出候选数中起来和等于T的所有组合。
C中的每个数字在一个组合中只能使用一次。
注意：

  1. 题目中所有的数字（包括目标数T）都是正整数
  2. 组合中的数字 (a1,a2,…,ak) 要按非递增排序 (a1≤a2≤…≤ak).
  3. 结果中不能包含重复的组合

二.算法(搜索+去重+剪枝)
例如：给定的候选数集是[10,1,2,7,6,1,5]，目标数是8
解集是：[[1, 7],[1, 2, 5],[2, 6],[1, 1, 6]]
图片说明
首先，对于这类寻找所有可行解的题，我们都可以尝试用搜素的方法来解决。我们采用深度优先搜素dfs(num, target,res,tmp,start)一共五个维度来进行搜索。
其中：

  • num:用来表示一组候选数组

  • target:用来表示每一个小组当前所需要的大小

  • res:用来存储每一个和为target的分组

  • tmp:用来暂时存储每一个分组

  • start:用来表示开始搜索的起点
    但是仅仅是想到搜索维度是不够的，无视搜索过程中重复搜索和无效搜索会造成超时，所以在搜索过程中要采用取去重和剪枝，下面直接看代码:

    class Solution {
public:
vector<vector<int> > combinationSum2(vector<int> &num, int target) {
  vector<vector<int> > res;
  vector<int> tmp;
  if (num.empty()) return res;
  sort(num.begin(), num.end());//对候选素组进行排序，在一定程度上可以优化搜索
  dfs(num, target, res, tmp, 0);//开始搜索 刚开始start=0 从第一个开始搜索
  return res;//返回最后的结果
}

void dfs(vector<int> &num, int target, vector<vector<int> > &res, vector<int> &tmp, int start) {
  if (target==0) {//当每一个小组的target=0的时候 说明该分组已经分好了 直接存进res中
      res.push_back(tmp);
      return;//末端终止 避免无效搜索
  }
  if (start>=num.size()) return;//当开始搜索的位置大于候选数字的时候 整个搜索结束
  for (int i=start;i<num.size(); ++i) {//从start到候选数组末尾开始搜索
      //去重处理 若相等 直接continue 避免重复搜索
      if (i>start&&num[i]==num[i-1]) continue;
      //剪枝
      //前面的排序就有意义了 这块要是剩余的num[i]的值已经大于target的大小 后面已经是无效搜索了
      if (num[i] <= target) { 
          //后面是一个回溯的过程先加入tmp 后从tmp末端删除 确保可以搜索可以进行下去
          tmp.push_back(num[i]);
          //由于num[i]加入 target的大小减去num[i] 搜索开始位置往后 也就是start+1
          dfs(num, target - num[i], res, tmp, i + 1);
          tmp.pop_back();
      }
  }
}
};

    时间复杂度：O(s)，其中s为所有可行解的长度之和。
    空间复杂度：O(n) 需要额外空间来返回值
    优缺点：便于实现，但是效率低，容易超时

三.算法(java实现)

本题目利用java同样可以实现，思路同上一个算法

import java.util.*;
public class Solution {
    public ArrayList<ArrayList<Integer>> combinationSum2(int[] num, int target) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> arr = new ArrayList<Integer>();
        if(num == null || num.length==0 || target<0)return res;
        Arrays.sort(num);//对候选数组进行排序 方便后续处理
        dfs(num,target,res,arr,0);
        return res;
    }
    void dfs(int[] num,int target,ArrayList<ArrayList<Integer>> res,ArrayList<Integer> arr,int start){
        if(target==0){
            //已找到一组 存储进res
            res.add(new ArrayList<Integer>(arr));
            return;
        }
        if(start >= num.length)return;
        for(int i=start;i<num.length;i++){
            if(i > start && num[i] == num[i-1])continue;
            //回溯操作
            if(num[i] <= target){
                arr.add(num[i]);
                dfs(num,target-num[i],res,arr,i+1);
                arr.remove(arr.size()-1);
            }
        }
        return;
    }
}

时间复杂度：O(s)，其中s为所有可行解的长度之和。
空间复杂度：O(n) 需要开辟空间存储结果
优缺点：便于实现，但是效率低，容易超时