回溯法——子集树和排列树

子集树：2^n（选还是不选的问题）
排列树：n！

子集树

当所给的问题是从n个元素的集合中找出满足某种性质的子集时，相应的解空间称为子集树。
算法描述为：

void backtrack(int t){
	if(t==n) output(x);
	else{
		for(int i=0;i<=1;++i){
			x[t]=i;//i=1表示选否则表示不选
			if(满足条件) backtrack(t+1);//若不满足条件则停止向下搜索，剪去该分支
		}
	}
}

排列树

当所给问题是确定n个元素满足某种性质的排列树时，相应的解空间称为排列树。
算法描述为：

void backtrack(int t){
	if(t==n) output(x);
	else{
		for(int i=t;i<n;++i){
			swap(x[t],x[i]);//下标为t的位置元素确定为x[i]
			if(满足条件) backtrack(t+1);//若不满足条件则停止向下搜索，剪去该分支
			swap(x[t],x[i]);//搜索完子树时回溯
		}
	}
}

回溯法——子集树和排列树

原文：https://www.cnblogs.com/Frank-Hong/p/13299915.html