无锡企业网站制作价格,培训网站项目ppt怎么做,我国好的室内设计公司排名,上海做衣服版的网站文章目录 一、题目二、解法三、完整代码 所有的LeetCode题解索引#xff0c;可以看这篇文章——【算法和数据结构】LeetCode题解。 一、题目 二、解法 思路分析#xff1a;【算法与数据结构】39、LeetCode组合总和的基础之上#xff0c;这道题变成了candidates中有重复元素可以看这篇文章——【算法和数据结构】LeetCode题解。 一、题目 二、解法 思路分析【算法与数据结构】39、LeetCode组合总和的基础之上这道题变成了candidates中有重复元素而且每个元素只能使用一次。如果直接使用39题的代码会出现重复的组合需要去重但这样一来leetcode可能运行超时。因此我们需要再找组合的时候就进行去重的操作。引入一个used布尔数组标记candidates中的元素是否使用过。在这之前首先需要对candidates数组进行排序。 例如 target7, candidates [1 1 2 4 5 7], 第一种情况candidates[0] candidates[2] candidates[3] candidates[1] candidates[2] candidates[3] 1 2 4, 因此出现重复的组合。第二种情况candidates[0] candidates[1] candidates[4] 1 1 5是无重复的组合。因此用used标记使用过的数当candidates[i] candidates[i - 1]时出现重复元素。进行第i次循环时第一种情况used[i-1]false就是出现重复组合, 在第i-1次循环时已经考虑过了直接continue。第二种情况就是重复数字都利用到了used[i-1]true这种需要考虑。 程序如下
class Solution {
private:vectorvectorint result; // 结果合集vectorint path;void backtracking(const vectorint candidates, const int target, int sum, int startIndex, vectorbool used) {if (sum target) return; // 剪枝if (sum target) {result.push_back(path);return;}for (int i startIndex; i candidates.size() sum candidates[i] target; i) { // 剪枝优化if (i 0 candidates[i] candidates[i - 1] used[i - 1] false) { // 去重continue; }sum candidates[i];used[i] true;path.push_back(candidates[i]); // 处理节点backtracking(candidates, target, sum, i1, used); // 递归used[i] false;sum - candidates[i];path.pop_back(); // 回溯撤销处理的节点}}
public:vectorvectorint combinationSum2(vectorint candidates, int target) {vectorboolused(candidates.size(), 0);sort(candidates.begin(), candidates.end());backtracking(candidates, target, 0, 0, used);return result;}
};复杂度分析
时间复杂度 O ( n ∗ 2 n ) O(n*2^n) O(n∗2n)。空间复杂度 O ( n ) O(n) O(n)。
三、完整代码
# include iostream
# include vector
# include string
# include algorithm
using namespace std;class Solution {
private:vectorvectorint result; // 结果合集vectorint path;void backtracking(const vectorint candidates, const int target, int sum, int startIndex, vectorbool used) {if (sum target) return; // 剪枝if (sum target) {result.push_back(path);return;}for (int i startIndex; i candidates.size() sum candidates[i] target; i) { // 剪枝优化if (i 0 candidates[i] candidates[i - 1] used[i - 1] false) { // 去重continue; }sum candidates[i];used[i] true;path.push_back(candidates[i]); // 处理节点backtracking(candidates, target, sum, i1, used); // 递归used[i] false;sum - candidates[i];path.pop_back(); // 回溯撤销处理的节点}}
public:vectorvectorint combinationSum2(vectorint candidates, int target) {vectorboolused(candidates.size(), 0);sort(candidates.begin(), candidates.end());backtracking(candidates, target, 0, 0, used);return result;}
};int main() {vectorint candidates { 10,1,2,7,6,1,5 };int target 8;Solution s1;vectorvectorint result s1.combinationSum2(candidates, target);for (vectorvectorint::iterator it result.begin(); it ! result.end(); it) {for (vectorint::iterator jt (*it).begin(); jt ! (*it).end(); jt) {cout *jt ;}cout endl;}system(pause);return 0;
}end
