回溯法是设计递归过程的一种重要方法,它的求解过程是遍历一个状态树,只是这颗树不是预先建立的而是隐含的遍历过程,在遍历过程中对各个元素进行取舍。
如求n个元素集合的子集,如A = {1, 2, 3}则A集合的子集有:
PrA = {{1,2,3}, {1,2}, {1,3},{1},{2,3},{2},{3},{}}
遍历过程中的状态树:
#include <iostream>
#include <stack>
using namespace std;
const int _N = 1000;
int list[_N];
int n;
void dfs(int i, int n, stack<int> s)
{
if(i == n)
{
cout<<"{";
while(!s.empty())
{
cout<<" "<<s.top();
s.pop();
}
cout<<"}"<<endl;
}else
{
s.push(list[i]); //取
dfs(i + 1, n, s);
s.pop(); //舍
dfs(i + 1, n, s);
}
}
int main()
{
int i;
while(cin>>n)
{
stack<int> s;
for(i = 0; i < n; i++)
list[i] = i + 1; //初始化
dfs(0, n, s);
}
return 0;
}
- 大小: 37.7 KB
分享到:
相关推荐
假设有个集合拥有m个元素,任意的从集合中取出n个元素,则这n个元素所形成的可能子集有那些?
试写一个递归算法实现求一个集合的所有子集。 算法设计: 给定一个非空的集合,用递归算法输出它的所有子集。 数据输入: 由文件input.txt 提供输入数据。文件第1行是集合中的元素个数,第2行是集合的元素序列(元素...
设S是有n(n≤20)个元素的集合,S的幂集是S所有可能的子集组成的集合。例如,S={a,b,c},则S的幂集={()(c)(b)(bc)(a)(ac)(ab)(abc)}。写一个C++递归程序,以S为输入,输出S的幂集。
求一个集合子集的算法示例, 用两种方法解,一种是基于回溯的递归求解,一种基于位域映射.
已知N个大于0的整数构成一个集合,即{1,2,3,……,N},求其所有的非空且元素不相邻的子集,计算所有子集的乘积的平方的和。
java实验--求一个集合的子集,非递归实现。
输出n个数集合的所有子集 c++课程实验 eclipse 编写
C/C++ 求一个集合的子集,代码易懂,好用,谢谢下载
Get subset of integers in a file named "source" ,which is in the same directory 即 求一个整数集合的子集,集合元素的个数不限, 采用读取文件的方式
【C++程序设计】组合函数C(n,k)是给定的n个元素中,由不同的k个元素组成的子集个数利用组合函数计算,编写阶乘及组合的函数,并在主函数中调用。适合新手
求一个集合的所有子集的C++实现
用于输出一个集合的所有子集,采用两种方法实现,值得一看!
# 给你一个整数数组 nums ,数组中的元素 互不相同 。返回该数组所有可能的子集(幂集)。 # 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。 # 示例 1: # 输入:nums = [1,2,3] # 输出:[[],[1],[2],[1...
接下来的1 行中,有n 个正整数,表示集合S 中的元素。 Output 程序运行结束时,将子集和问题的解输出到文件output.txt中。 当问题无解时,输出“No Solution!”。 Sample Input 5 10 2 2 6 5 4 Sample Output 2 ...
交错幂集是一种数学概念,它是由集合的所有子集的交错和构成的集合。...在递归过程中,通过跳过第k个元素来避免重复组合。在主函数中,我们调用computePermutations函数来计算交错幂集,并输出结果。
求集合的所有子集问题,提供的全部代码。 使用递归算法!
给定一个非空的集合,用递归算法输出它的所有子集。由文件input.txt 提供输入数据。文件第1行是集合中的元素个数,第2行是集合的元素序列(元素之间用空格分隔)。将计算出的所有子集分行输出到文件output.txt中。
输出n个字符(不限整数)的所有子集 C++ 数据结构 实验一
n 个元素的集合{1,2,., n }可以划分为若干个非空子集。给定正整数n 和m,计算出n 个元素的集合{1,2,., n }可以划分为多少个不同的由m 个非空子集组成的集合。