递归/回溯：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 <iostream>
#include <vector>
#include <algorithm>
#include <set>/*
已知一组数(其中有重复元素)，求这组数可以组成的所有子集中，子 集中的各个元素和为整数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]
总结：
递归回溯的结合，本身是时间复杂度较高的一种算法实现组合，但是如果能够合理运用给出的筛选条件，能够极大得缩短时间复杂度，使得代码更加简介高效。
相关文章：
如何在SharePoint2010中添加Deep Zoom Image
如何在SharePoint2010中添加Deep Zoom Image 应用范围 SharePoint 2010 Foundation；SharePoint 2010 Standard；SharePoint 2010 Enterprise所需材料 1. SeaDragon Ajax Viewer Web部件（点击此处下载）2. Deep Zoom Image Composer&…
linux 读取磁盘扇区,linux 下检查硬盘坏道/扇区
文章摘自：Linux检测硬盘坏道Linux检测硬盘坏道badblocks功能说明：检查磁盘装置中损坏的区块。语法：badblocks [-svw][-b ][-o ][磁盘装置][磁盘区块数][启始区块]补充说明：执行指令时须指定所要检查的磁盘装置，及此装置…
Pjax是什么以及为什么推荐大家用
什么是pjax? 现在很多网站( facebook, twitter) 都支持这样的一种浏览方式， 当你点击一个站内的链接的时候， 不是做页面跳转， 而是只是站内页面刷新。 这样的用户体验， 比起整个页面都闪一下来说， 好很多。 其中有一…
Scrapy框架CrawlSpider类爬虫实例
CrawlSpider类爬虫中： rules用于定义提取URl地址规则，元祖数据有顺序 #LinkExtractor 连接提取器，提取url地址 #callback 提取出来的url地址的response会交给callback处理 #follow 当前url地址的响应是否重新经过rules进行提取url地址 cf.py具…
递归/回溯：Generate Parentheses生成合法括号
已知n组括号，开发一个程序，生成这n组括号所有的合法的组合可能。 例如:n 3 结果为: ["((()))", “(()())”, “(())()”, “()(())”, “()()()”] 首先思考如何生成所有的括号组合的可能性，即例如2组括号，总共4个符号…
利用“哨兵”“实现双链表
利用“哨兵”“实现双链表 下面的代码用一个”哨兵“实现双链表，感觉很简洁，中间也有点绕，暂时实现，供学习之用 static Node list_handle {&list_handle,&list_handle, };bool addNode(Node* node) {if (node NULL){re…
suse linux显示乱码,open suse11.4中文乱码问题
winland0704 于 2011-04-07 00:56:10发表:不是乱码，而是字符编码标准不一样。windows的文本使用GBK，国标码。Linux使用Unicode编码。解决参看：hi.baidu.com/winland0704/blog/item/c58008512cc843c9b645aef1.html四、其他的一些问题3、文本编…
软件破解系列之OD中断方法
OD中断方法浅探 Ollydbg是一个新的32位的汇编层调试软件。适应于windows98、me、2000、xp和2003操作系统。由于他具有图形窗口界面，所以操作方便、直观，是cracker的好工具。 由于Ollydbg没有了TRW2000的万能断点，所以许多的新手感觉到用Ollyd…
MongoDB系列：二、MongoDB常用操作练习
最近在自学MongoDB，在此记录一下，当做学习笔记了（不断更新中）！！ 一、背景 MongoDB 是一个基于分布式文件存储的数据库。由 C 语言编写。旨在为 WEB 应用提供可扩展的高性能数据存储解决方案。它是一个介于关…
递归/回溯：八皇后问题N-Queens
N皇后问题是计算机科学中最为经典的问题之一，该问题可追溯到1848年，由国 际西洋棋棋手马克斯贝瑟尔于提出了8皇后问题。 将N个皇后放摆放在N*N的棋盘中，互相不可攻击，有多少种摆放方式，每种摆 放方式具体是怎样的? 8…
KS103超声波测距模块
max232：电平转换芯片，将电脑的RS-232标准串口（高12V，低-12V）转换为（高5V，低0V）。 电脑串口（RS -232） > 单片机串口（TTL串口） SIPEX…
linux 硬盘操作,linux常用disk磁盘操作命令
#按照目录大小排序战士最前面15个目录或者文件du -xB M --max-depth2 /var | sort -rn | head -n 15#列出当前所有子目录的文件大小du -h --max-depth1#列出当前文件或者目录最大的10个du -s * | sort -n | tail#按照目录大小从大到小排序du -b --max-depth 1 | sort -nr | per…
在Spring中采用声明式方法对Hibernate和JDBC进行统一的事务配置（AOP）
<?xml version"1.0" encoding"UTF-8"?><beans xmlns"http://www.springframework.org/schema/beans" xmlns:xsi"http://www.w3.org/2001/XMLSchema-instance" xmlns:aop"http://www.springframework.…
Leetcode 213.大家劫舍II
打家劫舍II 你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房…
替代Druid，HakariCP 为什么这么快？
这次源码探究，真的感觉看到了无数个小细节，无数个小优化，积少成多。平时开发过程中，一些小的细节也一定要“扣”。
递归/分治：归并排序
前言 分治算法: 将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出 子问题的解后进行合并，就可得到原问题的解。 步骤如下: 分解，将要解决的问题划分成若 干规模较小的同类问题;求解，…
Java中volatile 的使用场景有哪些？
volatile是一种轻量级的同步机制，它能保证共享变量的可见性，同时禁止重排序保证了操作的有序性，但是它无法保证原子性。所以使用volatilevolatile。
JDK22 正式发布了 ！
Java 22 除了推出了新的增强功能和特性，也获得 Java Management Service (JMS) 的支持，这是一项新的 Oracle 云基础设施远程软件服务(Oracle Cloud Infrastructure, OCI) 原生服务，提供统一的控制台和仪表盘，帮助企业管理本地或云端的 Java 运行时和应用。使包含运行时计算值的字符串更容易表达，简化 Java 程序的开发工作，同时提高将用户提供的值编写成字符串，并将字符串传递给其他系统的程序的安全性。支持开发人员自由地表达构造器的行为。
Jackson 用起来！
你可以创建自定义序列化器和反序列化器以自定义特定字段或类的序列化和反序列化行为。为此，请创建一个实现或接口的类，并在需要自定义的字段或类上使用和注解。@Override// ...其他代码...优势性能优异：Jackson在序列化和反序列化过程中表现出优秀的性能，通常比其他Java JSON库更快。灵活性：通过注解、自定义序列化器/反序列化器等功能，Jackson提供了丰富的配置选项，允许你根据需求灵活地处理JSON数据。易于使用：Jackson的API设计简洁明了，易于学习和使用。
Swift中的问号?和感叹号!
Swift语言使用var定义变量，但和别的语言不同，Swift里不会自动给变量赋初始值，也就是说变量不会有默认值，所以要求使用变量之前必须要对其初始化。如果在使用变量之前不进行初始化就会报错： var stringValue : String …
拜托！别再滥用 ! = null 判空了！！
另外，也许受此习惯影响，他们总潜意识地认为，所有的返回都是不可信任的，为了保护自己程序，就加了大量的判空。如果你养成习惯，都是这样写代码（返回空collections而不返回null)，你调用自己写的方法时，就能大胆地忽略判空）这种情况下，null是个”看上去“合理的值，例如，我查询数据库，某个查询条件下，就是没有对应值，此时null算是表达了“空”的概念。最终，项目中会存在大量判空代码，多么丑陋繁冗！，而不要返回null，这样调用侧就能大胆地处理这个返回，例如调用侧拿到返回后，可以直接。
ffmpeg java linux水印,Linux环境用FFmpeg给视频加水印详细步骤
FFmpeg给视频添加水印，根据官方文档的介绍可以知道FFmpeg在编译安装的时候还需要加 –enable-libfreetype、–enable-libfontconfig、 --enable-libfribidi 这几个参数，而这几个组件又需要从外面编译安装，我看很多博主直接用FFmpeg命令加水印…
red hat DHCP服务器配置
[ 基本操作 ] rpm –q dhcp / rpm -ql grep dhcp [ 查询DHCP ] yum –y install dhcp dhcp -devel service dhcpd start [ 启动 ] service dhcpd status [ 查看DHCP状态 ] chkconfig – level 3 5 dhcpd on [ 改变启动级别为3 5 自动启动服务 ] service ne…
axios解决调用后端接口跨域问题
vue-cli通过是本地代理的方式解决接口跨域问题的。但是在vue-cli的默认项目配置中这个代理是没有配置的，如果现在项目中使用，必须手动配置config/index.js文件 ... proxyTable: {/api: { //将www.exaple.com印射为/apistarget: https://www.example.c…
递归/归并：count of smaller numbers求逆序数
已知数组nums，求新数组count，count[i]代表了在nums[i]右侧且比 nums[i]小的元素个数。 例如: nums [5, 2, 6, 1], count [2, 1, 1, 0]; nums [6, 6, 6, 1, 1, 1], count [3, 3, 3, 0, 0, 0]; nums [5, -7, 9, 1, 3, 5, -2, 1], count [5, 0, 5, 1…
远程计划任务管理
有时你需要远程管理或运行一批机器，但是按要求你没有权限或者不能安装客户端，下面的批处理可能帮上你的忙，将下方代码保存为批处理，并创建Clients.txt，存放的是以回车分隔的IP echo off setlocal enabledelayedexpansi…
linux shell for 循环变量,shell for循环总结
1 shell for循环语法for 变量 in 列表docommand1command2...commandNdone1.1 读取列表中的值#!/bin/bashfor test in apple boy cat dogdoecho The next state is $testdone结果：The next state is appleThe next state is boyThe next state is catThe next state …
自定义堆栈（回文检测）
using System; using System.Collections;namespace CStack {class Program{static void Main(string[] args){CStack alist new CStack();string ch;string word "上海自来水来自海上";bool isPalindrome true;for (int x 0; x < word.Length; x){alist.Push…
二叉树(C++)：创建，前中后序遍历（递归+非递归），获取叶子节点个数，获取树的高度
文章目录前言创建二叉树先序遍历中序遍历后序遍历获取叶子节点个数获取树的高度测试代码前言 现有如下二叉树: 关于二叉树的相关操作，我们能够发现二叉树从根节点到子节点，以及每个中间节点基本都能够拆分为若干个子节点的操作，且每个子节点…
6月11号=》121页-125页
6.1 样式单概述 W3C已经给出了两种样式单语言的推荐标准，一种是级联样式单CSS(Cascading Style Sheets)， 另一种是可扩展样式单语言XSL(eXtensible Stylesheet Language)。 6.1.1 CSS CSS主要提供如下两个功能： 1：对页面的字…