dfs--全排列

输出自然数1到n所有不重复的排列，即n的全排列，要求所产生的任一数字序列中不允许出现重复的数字。

输入格式

n(1≤n≤9)

输出格式

由1～n组成的所有不重复的数字序列，每行一个序列。每个数字保留5个场宽

我们要把1到n个数字任意组合，且组合不重复，按照从小到大排序

vis数组：表示这个数字是否用到过

每次判断数字是否之前便使用过，如果没有使用过，即选择这个数字 vis[]=1，继续dfs，在dfs之后，把这个数字重新还原以便下次使用

1  for (int i = 1;i <= n;i++)
2     {
3         if (vis[i]==0)
4         {
5         vis[i] = 1;
6         a[x] = i;
7         dfs(x+1);
8         vis[i] = 0;
9     }

当重复过n次后，及证明每个数字都已经被选择，我们就从头输出

//给有一个整数n，1~n个数全排列 
#include <iostream>
#include <cstdio>
using namespace std;
bool vis[100];
int a[100];
int n;
void dfs(int x)
{
    if (x == n+1)
    {
        for (int i = 1;i <= n;i++)
        {
                printf ("%5d",a[i]);
        }
        cout<<endl;
        return;
    }
    for (int i = 1;i <= n;i++)
    {
        if (vis[i]==0)
        {
        vis[i] = 1;
        a[x] = i;
        dfs(x+1);
        vis[i] = 0;
    }
}
}
int main()
{
    scanf ("%d",&n); 
    dfs(1);
    return 0;
}

还有一些板子题也就一起放上来了

 1 //n个数是否能选出一些数使他们的和为k
 2 #include <cstdio>
 3 #include <iostream>
 4 #include <cstring>
 5 using namespace std;
 6 int n,k,a[100];
 7 bool vis[100],flag=0;
 8 void dfs(int x)
 9 {
10     if (x==n+1)
11     {
12         int ans = 0;
13         for (int i = 1;i <= n;i++)
14         {
15             if (vis[i])
16             {
17                 ans+=a[i];
18             }
19         }
20         if (ans==k)
21         flag=1;
22         return;
23     }
24     vis[x] = 1;
25     dfs(x+1);
26     vis[x] = 0;
27     dfs(x+1);
28 }
29 int main()
30 {
31     scanf ("%d%d",&n,&k);
32     for (int i = 1;i <= n;i++)
33     scanf ("%d",&a[i]);
34     dfs(1);
35     if (flag)
36     printf ("Yes");
37     else 
38     printf ("No");
39     return 0;
40  }

//在n个数里面任选k个 ，求所有情况乘积的和
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
int n,k,a[100];
bool vis[100];
int tmp = 0;
void dfs(int x,int count)
{
    if (count==k)
    {
        int ans = 1;
        for (int i = 1;i <= n;i++)
        {
            if (vis[i])
            {
                ans*=a[i];
            }
        }
        tmp+=ans;
        return ;
    }
    if (x==n+1)
    return ;
    vis[x] = 1;
    dfs(x+1,count+1);
    vis[x] = 0;
    dfs(x+1,count);
}
int main()
{
    scanf ("%d%d",&n,&k);
    for (int i = 1;i <= n;i++)
    {
        scanf ("%d",&a[i]);
    }
    dfs(1,0);
    cout<<tmp;
    return 0;
 }