回溯问题总结

一、子集问题

模板问题

给定一个序列[1,n],求这个序列的所有子集

输入描述：

一个正整数n(1 <= n <= 12)

输出描述：

每个子集一行，输出所有子集。

输出顺序为：

（1）元素个数少的子集优先输出；

（2）元素个数相等的两个子集A和B，若各自升序后满足前k−1项对应相同，但有Ak<Bk，那么将子集A优先输出（例如[1,5,9]比[1,5,10]优先输出）。

在输出子集时，子集内部按升序输出，子集中的每个数之间用一个空格隔开，行末不允许有多余的空格；空集用空行表

示。不允许出现相同的子集。

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;const int N = 13;vector<vector<int>> ans;
vector<int> temp;void dfs(int start, int n) {ans.emplace_back(temp);  // 将当前子集添加到结果中for (int i = start; i <= n; ++i) {  // 修改循环条件为 <= 以包含 ntemp.push_back(i);dfs(i + 1, n);temp.pop_back();}
}bool compare(vector<int> &a,vector<int> &b) {if (a.size() != b.size()) {return a.size() < b.size();}else {return a < b;}
}int main() {int n;scanf("%d", &n);dfs(1,n);sort(ans.begin(), ans.end(), compare);for (int i = 0; i < ans.size(); i++) {for (int j = 0; j < ans[i].size(); j++) {printf("%d", ans[i][j]);if (j + 1 < ans[i].size()) {printf(" ");}}printf("\n");}return 0;
}

变题：

小晴来参加一个游园会。游园会中有n个游戏项目，每个项目有且仅有一次参与机会，如果成功完成了任意一个项目，就能得到对应的积分；如果失败了，则积分不会发生变化。在游园会的出口可以用累计积分兑换奖品。小晴参与了所有项目，问最后小晴的累计积分有哪些可能。

输入描述

第一行一个正整数n（1≤n≤12），表示游戏项目的个数。

第二行为n个不超过100的正整数，表示每个游戏项目在成功完成后分别能获得多少积分。

输出描述

在一行内按升序输出所有不同的累计积分，数字之间用一个空格隔开，行末不允许有多余的空格。

同样是子集问题，为什么可以这么理解呢？因为对于小晴来说，他赢了可以拿对应的分，如果没有赢那么就不能选这个分加入结果，这不就是子集问题吗？

#include <cstdio>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;const int N = 13;
int a[N];
int n;
int path = 0;
set<int> res;// 子集问题void dfs(int start) {res.insert(path);  // 每次进入递归就把结果加入res中for (int i = start; i < n; ++i) {path += a[i];    dfs(i+1);path -= a[i];  // 回溯}
}int main() {scanf("%d",&n);for (int i = 0; i < n; ++i) {scanf("%d",&a[i]);}dfs(0);int idx = 0;for (set<int>::iterator it = res.begin(); it != res.end(); it++) {printf("%d", *it);printf(idx + 1 < res.size() ? " " : "\n");idx++;}return 0;
}

二、排列问题

题目描述

给定一个正整数n，假设序列S=[1,2,3,…,n]，求S的全排列。

输入描述

一个正整数n（1≤n≤8）。

输出描述

每个全排列一行，输出所有全排列。

输出顺序为：两个全排列A和B，若满足前k−1项对应相同，但有Ak<Bk，那么将全排列A优先输出（例如[1,2,3]比[1,3,2]优先输出）。

在输出时，全排列中的每个数之间用一个空格隔开，行末不允许有多余的空格。不允许出现相同的全排列。

#include <cstdio>
#include <vector>
using namespace std;const int MAXN = 8 + 1;
vector<vector<int> > result;
vector<int> path;
int n;
bool used[MAXN] = {false};void DFS(int idx) {if (idx == n + 1) {  result.push_back(path);return;}for (int i = 1; i <= n; i++) {if (!used[i]) {  // 这个数还没有选过进行选择path.push_back(i);used[i] = true;DFS(idx + 1);   // 此处的idx实际上是用来控制递归次数的used[i] = false;path.pop_back();}}
}int main() {scanf("%d", &n);DFS(1);for (int i = 0; i < result.size(); i++) {for (int j = 0; j < result[i].size(); j++) {printf("%d", result[i][j]);if (j != result[i].size() - 1){printf(" ");}}printf("\n");}return 0;
}

 变题:

题目描述

给定一个长度为n的序列，其中有n个可能重复的正整数，求该序列的所有全排列。

输入描述

第一行一个正整数n（1≤n≤8），表示序列中的元素个数。

第二行按升序给出n个可能重复的正整数（每个正整数均不超过100）。

输出描述

每个全排列一行，输出所有全排列。

输出顺序为：两个全排列A和B，若满足前k−1项对应相同，但有Ak<Bk，那么将全排列A优先输出（例如[1,2,3]比[1,3,2]优先输出）。

在输出时，全排列中的每个数之间用一个空格隔开，行末不允许有多余的空格。不允许出现相同的全排列。

看题目很明显还是排列问题，但是在这题中会有重复数字，比如我给出一个实例

输入：1，1，3，4

输出：1(第一个1)，1(第二个1)，3，4 和 1(第二个1)，1(第一个1)，3，4,是同一个排列

那么我们就需要剪枝了

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;const int MAXN = 8 + 1;
vector<vector<int> > result;
vector<int> temp;
int n, a[MAXN];
bool used[MAXN] = {false};void DFS(int idx) {if (idx == n) {result.push_back(temp);return;}for (int i = 0; i < n; i++) {if (i > 0 && a[i] == a[i - 1] && used[i - 1] == false) {continue;}if (!used[i]) {temp.push_back(a[i]);used[i] = true;DFS(idx + 1);used[i] = false;temp.pop_back();}}
}int main() {cin >> n;  for (int i = 0; i < n; i++) {cin >> a[i];  }DFS(0);sort(result.begin(), result.end());for (int i = 0; i < result.size(); i++) {for (int j = 0; j < result[i].size(); j++) {cout << result[i][j];  if (j + 1 < result[i].size()) {cout << " ";  } else {cout << endl;  }}}return 0;
}

三、组合问题

题目描述

给定两个正整数n、k，假设序列S=[1,2,3,…,n]，求从S中任选k个的所有可能结果。

输入描述

两个正整数n、k（1≤k≤n≤12）。

输出描述

每个组合一行，输出所有组合。

输出顺序为：两个组合A和B，若各自升序后满足前k−1项对应相同，但有Ak<Bk，那么将组合A优先输出（例如[1,5,9]比[1,5,10]优先输出）。

在输出组合时，组合内部按升序输出，组合中的每个数之间用一个空格隔开，行末不允许有多余的空格。不允许出现相同的组合

#include <cstdio>
#include <vector>
using namespace std;vector<vector<int> > result;
vector<int> temp;
int n, k;void DFS(int idx) {if (temp.size() == k) {result.push_back(temp);return;}for (int i = idx; i <= n; ++i) {temp.push_back(i);DFS(i+1);temp.pop_back();}
}int main() {scanf("%d%d", &n, &k);DFS(1);for (int i = 0; i < result.size(); i++) {for (int j = 0; j < result[i].size(); j++) {printf("%d", result[i][j]);printf(j + 1 < result[i].size() ? " " : "\n");}}return 0;
}

 变题：

题目描述

给定n个互不相同的正整数，从中选择若干个数（每个数只能选一次），使得这些数之和为定值K。求满足条件的方案数。

输入描述

第一行两个正整数n、K（1≤n≤12、1≤K≤128），分别表示整数个数与定值。

第二行按升序给出n个互不相同的正整数（每个正整数均不超过128）。

输出描述

输出满足条件的方案数。相同数字算作同一种方案，例如{2,3}和{3,2}是同一个方案（仅顺序不同）。

 这题显然是个组合问题，只是再原有的组合问题的基础上又提出了新的要求，即：和要为定制k

可以按照组合问题的模板来套，不过需要改变的是递归出口

#include <cstdio>
#include <vector>
using namespace std;int n,k;
const int N = 13;
int a[N];
int curr = 0;
int cnt;void dfs(int start) {if (curr > k) {return;}if (curr == k) {cnt++;return;}for (int i = start; i < n; ++i) {curr += a[i];dfs(i+1);curr -= a[i];}
}int main() {scanf("%d%d",&n,&k);for (int i = 0; i < n; ++i) {scanf("%d",&a[i]);}dfs(0);printf("%d",cnt);return 0;}