• 关键字:搜索、回溯
  • 难度:中
  • 题目大意:对于一个给出的数target和一个数集C,问存在多少种不同的方案,使得可以从数集C中选出若干个数(每个数可以选择无限次)使得这些数的和等于target。

题目描述

Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:

  • All numbers (including target) will be positive integers.
  • Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
  • The solution set must not contain duplicate combinations.

For example, given candidate set 2,3,6,7 and target 7,

A solution set is:

[7]

[2, 2, 3]

解法

感觉上LeetCode上这附近的题都是回溯性质的……

这道题还是挺有意思的,理论上如果主要求方案数的话应该是可以用动态规划一类的方法来完成,但是现在要输出所有方案的话,就可以直接使用回溯来进行解决了。

回溯是搜索的一种方法,即并不是搜索到一个目标结点(即一组方案)之后就结束搜索,而是要继续遍历接下来的所有方案,直到将整棵搜索树遍历完成即可。

在这里,对于这道题目的搜索,起始要维护的状态并不多——首先,我们可以很简单的确定我们的搜索方案,即先枚举方案中第一个数的值,然后再枚举第二个数的值,并保证第二个数要比第一个数大,……依次类推,直到已经枚举完成的数的和大于等于target,然后通过检查是否等于target来判断是否要将这组方案记录下来。

也就是说,我们需要记录这样几个状态current-表示当前已经枚举完成的组合,last_use-上一个使用的数字在candidates中的下标(记录下标是为了方便枚举),rest_target-target剪去之前枚举完成的数之后的剩余,虽然理论上last_use和rest_target都可以通过current计算出,但是为了避免重复计算带来的时间复杂度提升,我们这里还是将其列入状态之中。

也就是说,我们的回溯方法声明是这样子的:

void backtracking(vector<vector<int>>& ans, vector<int>& candidates, vector<int> current, int last_use, int rest_target) {
}

其中ans和candidates是为了避免全局变量的定义而传入的引用参数。

在有了这基础之后,按照分类讨论从简单分支开始的原则,我们先判断边界情况——即rest_target==0的情况(为什么不讨论<0的情况在之后说明),即

        // 当rest_target等于0时,说明已经找到了一组合法的方案
        if (rest_target == 0) {
            // 故将其加入到答案当中
            ans.push_back(current);
        }

否则就应当枚举下一个放入current中的数字,即

        // 否则就枚举下一个加入到current中的数,在枚举中注意2个条件
        // i >= last_use,保证current是非递减的
        // candidates[i] <= rest_target,保证rest_target不小于0
        for (int i = last_use; i < candidates.size() && candidates[i] <= rest_target; i++) {
            // 放入current中
            current.push_back(candidates[i]);
            // 继续搜索下一个数字
            backtracking(ans, candidates, current, i, rest_target - candidates[i]);
            // 回溯处理
            current.pop_back();
        }

这样,整个回溯方法就完成了,在这基础上,还要注意对一些变量的初始化和对Candidates的排序,这样,这道题目就可以轻松完成了。

参考代码

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        // 注意candidates不是有序的,要先排序处理
        sort(candidates.begin(), candidates.end());
        // 用以记录答案和当前方案
        vector<vector<int>> ans;
        vector<int> current;
        // 开始回溯搜索
        backtracking(ans, candidates, current, 0, target);
        // 返回答案
        return ans;
    }
    
    void backtracking(vector<vector<int>>& ans, vector<int>& candidates, vector<int> current, int last_use, int rest_target) {
        // 当rest_target等于0时,说明已经找到了一组合法的方案
        if (rest_target == 0) {
            // 故将其加入到答案当中
            ans.push_back(current);
        }
        // 否则就枚举下一个加入到current中的数,在枚举中注意2个条件
        // i >= last_use,保证current是非递减的
        // candidates[i] <= rest_target,保证rest_target不小于0
        for (int i = last_use; i < candidates.size() && candidates[i] <= rest_target; i++) {
            // 放入current中
            current.push_back(candidates[i]);
            // 继续搜索下一个数字
            backtracking(ans, candidates, current, i, rest_target - candidates[i]);
            // 回溯处理
            current.pop_back();
        }
    }
};

登录发表评论 注册

反馈意见