首页 > 递归/回溯：Combination Sum II数组之和

递归/回溯：Combination Sum II数组之和

问题如下：

已知一组数(其中有重复元素)，求这组数可以组成的所有子集中，子 集中的各个元素和为整数target的子集，结果中无重复的子集。

例如: nums[] = [10, 1, 2, 7, 6, 1, 5]， target = 8

结果为: [[1, 7], [1, 2, 5], [2, 6], [1, 1, 6]]

同样之前有类似的相关的问题递归/回溯：Subsets II求子集（有重复元素）,最终将子集中和为8的集合输出，同样不能有重复子集

一个直接的办法就是在输出最终子集的时候，使用之前类似的问题解决过程，将初始筛选的集合做一个计算，检查是否满足target 为8的要求，满足则返回。

类似如下:

std::vector<std::vector<int> > get_subsets(std::vector<int> &num ,int target) { std::vector<int> item;std::vector<std::vector<int>> result;std::set<std::vector<int> > uniq_result;sort(num.begin(), num.end());result.push_back(item);generate(0, num, item, result, uniq_result);/*对递归回溯获取到的结果进行计算，将满足要求的和为target的子集筛选出来返回*/int sum; std::vector<std::vector<int>> target_result;for (int i = 0; i< result.size(); ++i){ sum = 0;for (int j = 0; j < result[i].size(); ++j) { sum += result[i][j];}if (sum == target) { target_result.push_back(result[i]);}}return target_result;
}

但是一个很严重的问题，递归/回溯本身是2^n的复杂度，如果仍然按照以上的方法对所有元素筛选一遍之后再返回显然时间复杂度极高，并且在回溯过程中没有应用到要求的target条件

提出如下方法，在回溯的过程中进行计算，当计算过程中有超过target的集合或者元素，即可终止继续递归，直接回溯，防止没有意义的递归下去。

类似[10,1,2,3,5],其中包含10的子集显然没有必要加入到最终的集合，因为10已经大于target了

实现算法如下:

oid generate(int i, std::vector<int> &num,std::vector<int> &item,std::vector<std::vector<int> > &result,std::set<std::vector<int> > &uniq_result,int sum, int target) { /*当结果大于target，直接返回，没有必要继续递归*/if (sum > target || i >= num.size()) { return;}sum += num[i];item.push_back(num[i]);/*满足结果为target,且不是重复子集，则加入到最终的结果中*/if (sum == target && uniq_result.find(item) == uniq_result.end()) { result.push_back(item);uniq_result.insert(item);}generate(i + 1, num, item, result, uniq_result, sum, target);item.pop_back();sum -= num[i];generate(i + 1, num, item, result, uniq_result, sum, target);
}std::vector<std::vector<int> > get_combiname_sets(std::vector<int> &num, int target) { std::vector<int> item;std::vector<std::vector<int>> result; //存储最终的子集std::set<std::vector<int> > uniq_result; //集合，筛选重复子集sort(num.begin(),num.end());generate(0, num, item, result, uniq_result, 0, target);return result;
}

测试代码如下:

nums[] = [10, 1, 2, 7, 6, 1, 5]， target = 8

#include 
#include 
#include 
#include /*
已知一组数(其中有重复元素)，求这组数可以组成的所有子集中，子 集中的各个元素和为整数target的子集，结果中无重复的子集。
例如: nums[] = [10, 1, 2, 7, 6, 1, 5]， target = 8
结果为: [[1, 7], [1, 2, 5], [2, 6], [1, 1, 6]]
*/using namespace std;void generate(int i, std::vector<int> &num,std::vector<int> &item,std::vector<std::vector<int> > &result,std::set<std::vector<int> > &uniq_result,int sum, int target) { if (sum > target || i >= num.size()) { return;}sum += num[i];item.push_back(num[i]);if (sum == target && uniq_result.find(item) == uniq_result.end()) { result.push_back(item);uniq_result.insert(item);}generate(i + 1, num, item, result, uniq_result, sum, target);item.pop_back();sum -= num[i];generate(i + 1, num, item, result, uniq_result, sum, target);
}std::vector<std::vector<int> > get_combiname_sets(std::vector<int> &num, int target) { std::vector<int> item;std::vector<std::vector<int>> result;std::set<std::vector<int> > uniq_result;sort(num.begin(),num.end());generate(0, num, item, result, uniq_result, 0, target);return result;
}int main(int argc, char const *argv[])
{ std::vector<int> num;std::vector<int> item;std::vector<std::vector<int>> result;int tmp;int N;std::cin >> N;for (int i  = 0;i < N; ++i) { std::cin >> tmp;num.push_back(tmp);}int target;cin >> target;result= get_combiname_sets(num,target);for (int i = 0;i < result.size(); ++i) { for (int j = 0;j < result[i].size(); ++j) { std::cout << "[" << result[i][j] << "] ";}std::cout << std::endl;}return 0;
}

输出如下:

#输入
7
10 1 2 7 6 1 5
8#结果
[1] [1] [6] 
[1] [2] [5] 
[1] [7] 
[2] [6]

总结：

递归回溯的结合，本身是时间复杂度较高的一种算法实现组合，但是如果能够合理运用给出的筛选条件，能够极大得缩短时间复杂度，使得代码更加简介高效。

更多相关：

  • 基于C++实现线程池加速

    经过长期探索，发现一个不需要手动设置线程休眠时间(e.g. std::this_thread::sleep_for(std::chrono::microseconds(1)))的代码: Github: https://github.com/log4cplus/ThreadPool #ifndef THREAD_POOL_H_7e...

  • STL nth_element

    nth_element(first,nth,last) first，last 第一个和最后一个迭代器，也可以直接用数组的位置。  nth，要定位的第nn 个元素，能对它进行随机访问. 将第n_thn_th 元素放到它该放的位置上，左边元素都小于它，右边元素都大于它. 测试代码: http://www.cplusplus.com...

  • c++11随机数产生器default_random_engine

    c/c++老版本的rand（）存在一定的问题，在转换rand随机数的范围，类型或者分布时，常常会引入非随机性。 定义在 中的随机数库通过一组协作类来解决这类问题：随机数引擎 和 随机数分布类 一个给定的随机数发生器一直会生成相同的随机数序列。一个函数如果定义了局部的随机数发生器，应该将（引擎和分布对象）定义为 st...

  • Jsoncpp 在C++开发中的一些使用记录

    jsoncpp 是一个C++ 语言实现的json库，非常方便得支持C++得各种数据类型到json 以及 json到各种数据类型的转化。 一个json 类型的数据如下： {"code" : 10.01,"files" : "","msg" : "","uploadid" : "UP000000" } 这种数据类型方便我们人阅读以...

  • java 读取excel_Java12POI操作Excel

            Apache POI是一个开源的利用Java读写Excel，WORD等微软OLE2组件文档的项目。        我的需求是对Excel的数据进行导入或将数据以Excel的形式导出。先上简单的测试代码：package com.xing.studyTest.poi;import java.io.FileInputSt...

  • C++ 生成随机数

    要取得[a,b)的随机整数，使用(rand() % (b-a))+ a; 要取得[a,b]的随机整数，使用(rand() % (b-a+1))+ a; 要取得(a,b]的随机整数，使用(rand() % (b-a))+ a + 1; 通用公式:a + rand() % n；其中的a是起始值，n是整数的范围。 要取得a到b之间的...

  • 基于C++的本征图像分解(Intrinsic Image Decomposition)

    利用本征图像分解(Intrinsic Image Decomposition)算法，将图像分解为shading(illumination) image 和 reflectance(albedo) image，计算图像的reflectance image。 Reflectance Image 是指在变化的光照条件下能够维持不变的图像部分...

  • 剑指offer：面试题39. 数组中出现次数超过一半的数字

    题目：面试题39. 数组中出现次数超过一半的数字 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。 你可以假设数组是非空的，并且给定的数组总是存在多数元素。 示例 1: 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2] 输出: 2 限制： 1 <= 数组长度 <= 50000 解题： cl...

  • 剑指offer：面试题33. 二叉搜索树的后序遍历序列

    题目：二叉搜索树的后序遍历序列 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。 参考以下这颗二叉搜索树：      5     /    2   6   /  1   3示例 1： 输入: [1,6,3,2,5] 输出...

  • 基于SfM计算相机姿态

    具体过程为： ① 通过相机标定方法，预先计算相机的内参矩阵； ② 相邻帧特征点匹配，并结合内参矩阵计算本征矩阵； ③ 本征矩阵分解获得相机的外参矩阵[R | T]，最终的相机移动距离等于矩阵T的Frobenius范数。 #include #include

  • 剑指offer：面试题34. 二叉树中和为某一值的路径

    题目：二叉树中和为某一值的路径 输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。 示例: 给定如下二叉树，以及目标和 sum = 22，               5              /             4   8    ...

  • vector容器 begin()与end()函数、front()与back()的用法

    begin函数： 函数原型: iterator begin(); const_iterator begin(); 功能： 返回一个当前vector容器中起始元素的迭代器。 end函数： 函数原型： iterator end(); const_iterator end(); 功能： 返回一个当前vector容器中末尾元素的迭代器。...

  • C++ STL: 容器vector源码分析

    文章目录前言vector的核心接口vector push_back实现vector 的 Allocatorvector 的 push_back总结...

  • leetcode-102 二叉树的层次遍历

    给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。 例如: 给定二叉树: [3,9,20,null,null,15,7] 3 / 9 20 / 15 7 返回其层次遍历结果： [ [3], [9,20], [15,7] ] 方法一（非递归） 二叉树的层次遍历即二叉树的广度遍历，可以使...

©2024 11GX.COM