题目描述

• Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target.

• Each number in candidates may only be used once in the combination.

• Note: The solution set must not contain duplicate combinations.

• Constraints:

  • 1 <= candidates.length <= 100
  • 1 <= candidates[i] <= 50
  • 1 <= target <= 30

• 现给出一个整型数字的候选聚集（candidates）和一个目标数字（target），找到集合中的所有的组合，组合中的所有的数字和为target。

• 在集合中的数字每一个都仅仅可以使用一次。

• 注意：最终的答案的集合，一定不可以包含重复的数字。

测试样例

• Example 1:

  • Input: candidates = [10,1,2,7,6,1,5], target = 8
  • Output:
    • [
    • [1,1,6],
    • [1,2,5],
    • [1,7],
    • [2,6]
    • ]

• Example 2:

  • Input: candidates = [2,5,2,1,2], target = 5
  • Output:
    • [
    • [1,2,2],
    • [5]
    • ]

回溯解决

思路分析

• 这里对比上一道题，Combination Sum（传送门）只是增加了一个条件，就是不重复，那这个问题就好做多了。
• 那就是在上一道题的基础上改变一下回溯的策略就可以了。

实现的源码

#include <iostream>
#include <vector>
#include <sstream>
#include <algorithm>

using namespace std;


//下述为使用回溯解决的算法
vector<vector<int>>  result;
vector<int> current;

/*
 * 描述：回溯递归函数
 * 参数：candinates是保存候选数集合
 *      start是每一次开始遍历初始值
 *      remian是当前值和目标值的之间的差值
 * 返回：无，直接将最终的结果保存到全局变量中
 */
void helper(vector<int>& candinates,int start,int remain){

    //差值为零，表示两者可以完全的适合
    if(remain == 0){
        for (auto i = result.begin(); i != result.end(); ++i) {
            if(*i == current)   return;
        }
        result.push_back(current);
    } 

    //remain表示的两者之间的差值小于零，说明不能再相加剩余的数字了
    if(remain < 0)  return;

    //下述说明还可以继续增加对应的数字
    for (int i = start; i < candinates.size(); ++i) {
        current.push_back(candinates[i]);
        //if(constraint()){
            //满足约束条件，就往下进行遍历
        helper(candinates,i+1,remain-candinates[i]);

        //}
        current.pop_back();

    }
}

/*
 * 描述：对于不可重复的数字组合求和问题
 * 参数：candinates数字候选集
 *      target求取的目标
 * 返回：所有组合构成的vector
 */
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {

    //对候选数列进行排序
    sort(candidates.begin(),candidates.end());

    //如果当前为空
    if (candidates.empty())  return result;

    //开始继续往下遍历
    helper(candidates,0,target);
    return result;

}

int main() {
    //处理输入[1,2,3]，将首尾的括号去掉，并使用逗号将数组进行分割
    //定义一个vector变量
    vector<int> nums;
    string a ;
    getline(cin,a);
    int target = 0;
    cin>>target;


    a = a.erase(0,1);
    a = a.erase(a.size()-1,1);

    //对字符串进行分割
    stringstream sstr(a);
    string token;
    while(getline(sstr,token,',')){
        nums.push_back(atoi(token.c_str()));
    }

    //调用函数并直接输出
    vector<vector<int>> result;
    vector<int>* pointer = NULL;
    result = combinationSum2(nums,target);

    //输出结果进行验证
    for (int i = 0; i < result.size(); ++i) {
        for (int j = 0; j < result.at(i).size(); ++j) {
            pointer = &result.at(i);
            cout<<pointer->at(j);
        }
        cout<<endl;
    }

    return 0;
}

提交过程

部分代码讲解

• 如果去掉对整个数组的排序，因为candidate是一个collection，其中的元素是可以重复的，但是题目要求形成的combination不可以相同。

  • 比如测试样例中，[10,1,2,7,6,1,5]，可以形成的[1,7]和[7,1]实际上是由两个1组成，但是最终的result要求是一个set，意味着其中不能相同的元素，所以就需要将这种情况去除

• 关于迭代条件的变化，这里是有两个条件，start和remain
  • start表示下一层开始遍历的起点，之前用过的数字，在被后面的数字利用，比如针对[1,2,3]，如果不指定开始的位置，就会出现如下的情况。[1,2,3]和[1,3,2]等情况。
  • remain表示当前的current中的元素之和和最终的target之间的差值，差值越小则表示越接近。

• 关于递归整体的代码，只想说每一次迭代改变了那些，发生水平方向上的迭代时，就要将改变的变回来，才可以进行水平迭代。

分析与总结

• 回溯算法很棒，很灵活但是有很多变式和细节，需要自己在使用中不断体会，加深。实际上就是排列组合问题具体实现，不过方式不同。