求给定集合的幂集
数据结构中说这个问题可以用类似8皇后的状态树解法。
把求解过程看成是一棵二叉树，空集作为root，然后遍历给定集合中的元素，左子树表示取该元素，右子树表示舍该元素。
然后，root的左右元素分别重复上述过程。
就形成了一个递归。
集合使用List--单链表来存储，这样能保证，取和舍都只影响链表中的一个节点。
代码如下：
#include <iostream>
using namespace std;/**
*单链表的实现。
*/
class Node{
public:char ele;Node * next;Node(char ele): ele(ele), next(NULL){}~Node(){if(next) delete next;}void printNode(){cout<<ele<<" ";}
};
class list{Node *header;int length;
public:list(): header(NULL), length(0){}~list(){if(header)delete header;}void addNode(Node *n){if(header == NULL){header = n;length++;}else{Node *tmp = header;while(tmp->next != NULL){tmp = tmp->next;}tmp->next = n;length++;}}void deleteNode(char value){if(header == NULL){return;}Node *tmp = header;Node *pre = header;while(tmp!= NULL){if(tmp->ele == value){if(tmp == header){delete header;header = NULL;}else{pre->next = tmp->next;tmp->next = NULL;delete tmp;length--;}}else{pre = tmp;tmp = tmp->next;}}}void printList(){if(header == NULL || length == 0){return;}Node* tmp = header;while(tmp != NULL){tmp->printNode();tmp = tmp->next; }cout<<endl;}};static list *l;//链表
const char *source;//源字符串
void getPowerSet(int i, int n);//函数声明//初始化
void initSet(const char *src){l = new list;source = src;
}//取操作
void addPowerSet(int i, int n){l->addNode(new Node(source[i]));getPowerSet(i + 1, n);
}//舍操作
void deletePowerSet(int i, int n){l->deleteNode(source[i]);getPowerSet(i + 1, n);
}//入口函数
void getPowerSet(int i, int n){if(i > n){cout<<"one result: ";l->printList();//打印出一个结果，说明一个分支已经走完，拿到了一个子集。return;}else{addPowerSet(i, n);//取deletePowerSet(i, n);//舍}
}
//main函数
int main(){initSet("123");getPowerSet(0, 2);delete l;return 0;
}相关文章：
angular 命令行项目_Angular命令行界面介绍
angular 命令行项目Angular is closely associated with its command-line interface (CLI). The CLI streamlines generation of the Angular file system. It deals with most of the configuration behind the scenes so developers can start coding. The CLI also has a l…
oracle-imp导入小错filesize设置
***********************************************声明*********************************************************************** 原创作品，出自 “深蓝的blog” 博客。欢迎转载，转载时请务必注明出处。否则追究版权法律责任。表述有错误之处…
CentOS 7 下用 firewall-cmd / iptables 实现 NAT 转发供内网服务器联网
自从用 HAProxy 对服务器做了负载均衡以后，感觉后端服务器真的没必要再配置并占用公网IP资源。 而且由于托管服务器的公网 IP 资源是固定的，想上 Keepalived 的话，需要挤出来 3 个公网 IP 使用，所以更加坚定了让负载均衡后端服务器…
八皇后的一个回溯递归解法
解法来自严蔚敏的数据结构与算法。 代码如下： #include <iostream> using namespace std; const int N 8;//皇后数 int count 0;//解法统计 int a[N][N];//储存值的数组const char *YES "■"; const char *NO "□"; //const char *Y…
即时编译和提前编译_即时编译说明
即时编译和提前编译Just-in-time compilation is a method for improving the performance of interpreted programs. During execution the program may be compiled into native code to improve its performance. It is also known as dynamic compilation.即时编译是一种提…
bzoj 2588 Spoj 10628. Count on a tree （可持久化线段树）
Spoj 10628. Count on a tree Time Limit: 12 Sec Memory Limit: 128 MBSubmit: 7669 Solved: 1894[Submit][Status][Discuss]Description 给定一棵N个节点的树，每个点有一个权值，对于M个询问(u,v,k)，你需要回答u xor lastans和v这两个节点…
.Net SqlDbHelper
using System.Configuration; using System.Data.SqlClient; using System.Data;namespace ExamDAL {class SqHelper{#region 属性区// 连接字符串private static string strConn;public static string StrConn{get{return ConfigurationManager.ConnectionStrings["Exam&…
C语言的一个之前没有见过的特性
代码： #include <stdio.h>int test(){int a ({int aa 0;int bb 1;int cc 2;if(aa 0 && bb 1)printf("aa %d, bb %d\n", aa, bb);//return -2;cc;});return a; }int main(){typeof(4) a test();printf("a %d\n", a); } …
如何构建顶部导航条_如何构建导航栏
如何构建顶部导航条导航栏 (Navigation Bars) Navigation bars are a very important element to any website. They provide the main method of navigation by providing a main list of links to a user. There are many methods to creating a navigation bar. The easiest…
SPSS聚类分析：K均值聚类分析
SPSS聚类分析：K均值聚类分析 一、概念：（分析-分类-K均值聚类） 1、此过程使用可以处理大量个案的算法，根据选定的特征尝试对相对均一的个案组进行标识。不过，该算法要求您指定聚类的个数。如果知道ÿ…
[ 总结 ] nginx 负载均衡 及 缓存
操作系统：centos6.4 x64 前端使用nginx做反向代理，后端服务器为：apache php mysql 1. nginx负载均衡。 nginx编译安装（编译安装前面的文章已经写过）、apache php mysql 直接使用yum安装。 nginx端口：80…
中国剩余定理(孙子定理)的证明和c++求解
《孙子算经》里面的"物不知数"说的是这样的一个题目：一堆东西不知道具体数目，3个一数剩2个，5个一数剩3个，7个一数剩2个，问一共有多少个。 书里面给了计算过程及答案：70*2 21*3 15*2 -105*2 2…
osi七层网络层_OSI层速成课程
osi七层网络层介绍 (Introduction) Have you ever wondered how data is sent through the network from one machine to another? If yes, then the Open System Interconnected model is what you are looking for.您是否曾经想过如何通过网络将数据从一台机器发送到另一台机…
KMP算法求回溯数组的步骤
KMP算法到底是什么原理就不说了，各种资料上讲的明明白白，下面我就如何用代码来实现做一下说明和记录. KMP的核心思想就是，主串不回溯，只模式串回溯。而模式串匹配到第几位时失配，要回溯多少，由模式串本身来…
【.Net】vs2017 自带发布工具 ClickOnce发布包遇到的问题
一、遇到的问题 在安装了vs2017 社区版（Community）之后 想打包安装程序（winform） 还是想用之前的 installshield来打包 发现居然打不了，在官网查了 installshield不支持社区版（Community）&…
windows平台，开发环境变量配置
1.打开我的电脑--属性--高级--环境变量 JAVA配置环境变量变量名：JAVA_HOME 变量值：C:\Program Files\Java\jdk1.7.0 变量名：CLASSPATH 变量值：.;%JAVA_HOME%\lib\dt.jar;%JAVA_HOME%\lib\tools.jar; 变量名：Path 变…
如何编写可测试的代码 哈利勒的方法论
Understanding how to write testable code is one of the biggest frustrations I had when I finished school and started working at my first real-world job. 当我完成学业并开始从事第一份现实世界的工作时，了解如何编写可测试的代码是我最大的挫败之一。 T…
【Java入门提高篇】Day6 Java内部类——成员内部类
内部类是什么，简单来说，就是定义在类内部的类（一本正经的说着废话）。 一个正经的内部类是长这样的： public class Outer {class Inner{} } 这是为了演示而写的类，没有什么luan用，可以看到Inner类…
POJ 1001(高精度乘法 java的2种解法)
方法1: import java.math.BigDecimal; import java.util.Scanner; public class Main {public static void main(String[] args) {Scanner sc new Scanner(System.in);while(sc.hasNext()){String d sc.next();int z sc.nextInt();BigDecimal bd new BigDecimal(d);BigDeci…
Java编写的电梯模拟系统《结对作业》
作业代码：https://coding.net/u/liyi175/p/Dianti/git 伙伴成员：李伊 http://home.cnblogs.com/u/Yililove/ 对于这次作业，我刚开始一点思绪都没有，在老师安排了结对伙伴李伊之后，我的搭档问我，我们需要什么…
HTML属性说明
HTML elements can have attributes, which contain additional information about the element.HTML元素可以具有属性，其中包含有关该元素的其他信息。 HTML attributes generally come in name-value pairs, and always go in the opening tag of an element. Th…
css中的选择器
1.在html中引入css的方法：四种方式: a.行内式(也称内联式) 如: <h1 style"color:red;test</h1> b.内嵌式 <style type"text/css"> h1{ color:red; font-size: 10.5pt; font-family: Calibri, sans-serif; line-height: normal; widow…
javascript的call()方法与apply()方法的理解
先看一段代码 function cat() {} cat.prototype{food:fish,say:function () {console.log(I love this.food);} };var blackCat new cat(); blackCat.say(); 这时，控制台输出 I love fish若此时，有另一个对象 Dog{food:bones and shit}; dog对象没有say…
java排序算法(冒泡，插入，选择，快速，堆，归并，希尔，基数)
import java.util.Arrays; import java.util.LinkedList;/*** * * 各种排序: 冒泡，插入，选择，快速，堆，归并，希尔，基数*/ public class Sorts {//1. 冒泡：//时间复杂度:n(n-1)/2O(n^2…
边界填充算法讲解_边界填充算法
边界填充算法讲解Boundary fill is the algorithm used frequently in computer graphics to fill a desired color inside a closed polygon having the same boundary color for all of its sides.边界填充是在计算机图形学中经常使用的算法，用于在其所有边都具有…
使用Git管理源代码
git是个了不起但却复杂的源代码管理系统。它能支持复杂的任务，却因此经常被认为太过复杂而不适用于简单的日常工作。让我们诚实一记吧：Git是复杂的，我们不要装作它不是。但我仍然会试图教会你用（我的）基本的Git和远程代…
[.Net跨平台]部署DTCMS到Jexus遇到的问题及解决思路---Linux环境搭建
最近朋友托我帮忙研究如何把一个DTCMS部署到Linux下，经过1天的研究，部署基本成功，可能有些细节还未注意到，现在把心得分享一下。过程比预期的要简单 身为.Net程序员，这个问题的第一步可能就是如何搭建一个Linux环境来测…
Sequence point 中文
摘自维基百科： In C[4] and C,[5] sequence points occur in the following places. (In C, overloaded operators act like functions, and thus operators that have been overloaded introduce sequence points in the same way as function calls.) Between ev…
python中pop函数_Python中的Pop函数
python中pop函数什么是弹出功能？ (What is the pop function?) The method pop() removes and returns the last element from a list. There is an optional parameter which is the index of the element to be removed from the list. If no index is specified…
第六周学习进度条
日期 任务 听课 编程 阅读 准备考试 日总计 周日 周一 120 300 0 0 420 100 周二 0 120 0 0 120 周三 0 0 0 0 0 周四 0 0 0 0 0 周五 0 0 0 0 0 周六 0 120 100 0 …