DFS（修改）

例3：组合问题

输出m个数中取n个数的所有组合。

例如m=5，n=3的所有组合为：

1 2 3

1 2 4

1 2 5

1 3 4

1 3 5

1 4 5

2 3 4

2 3 5

2 4 5

3 4 5

#include<iostream>

using namespace std;

int m,n,a[10]; //存放每个数

void comb(int k)

{ if ( k>n )

{ for (int i=1; i<=n;i++)printf("%5d",a[i]);

printf(" ");

}

else

for (int i=a[k-1]+1; i<=m-n+k; i++)

{ a[k]=i; comb(k+1); }

}

int main( )

{ scanf("%d%d",&m,&n);

comb(1); //从第1个数开始

}

#include<iostream> using namespace std;

int m,n,a[10]; //存放每个数

void comb(int k)

{ if ( k>n )

{ for (int i=1; i<=n;i++) cout<<a[i]<<" ";

cout<<endl;

}

else

for (int i=a[k-1]+1; i<=m-n+k; i++)

{ a[k]=i; comb(k+1); }

}

int main( )

{

cin>>m>>n;

comb(1); //从第1个数开始

}

例4：子集问题

给定一个有n个元素的集合，输出它所有可能的子集（共2ⁿ个）。

例如3个数1、2、3的所有子集为：

空集

1 2

1 3

1 2 3

2 3

#include<iostream> using namespace std;

int m,n,a[10]; //存放每个数

void DFS(int k)

{

for (int i=0; i<k; i++)

cout<<a[i]<<" ";

cout<<endl;

int min = k>a[k-1]+1 ? k : a[k-1]+1;

for (int i=min; i<=m; i++)

{ a[k]=i; DFS(k+1); }

} int main()

{ cin>>m;

// for (int i=0; i<m; i++) a[i]=i+1;

DFS(0); return 0;

}

// 子集问题 dfs代码1

#include<iostream>

using namespace std;

int m,n,a[10]; //存放每个数

void DFS(int k)

{ for (int i=0; i<k; i++) cout<<a[i]<<" ";

cout<<endl;

for (int i= a[k-1]+1; i<=n; i++)

{ a[k]=i; DFS(k+1); }

}

int main()

{ cin>>n;

DFS(0); return 0;

}

**************************************************************************

0 0 0 ---------0

0 0 1 ---------1 3

0 1 0 ---------2 2

0 1 1 ---------3 2 3

1 0 0 ---------4 1

1 0 1 ----------5 1 3

1 1 0 ---------6 1 2

1 1 1 ----------7 1 2 3

#include <iostream>
using namespace std;
int n,m, a[10];
void  DFS(int k)
{   if  (k>n) 
    {  for (int i=1; i<=n; i++)     
          
          cout<<a[i]<<" ";
       cout<<endl;   
    }
    else 
       for (int i=0; i<=1; i++)   
       {    a[k]=i;    DFS(k+1);      }
}
int main()
{        cin>>n;         DFS(1);    return 0;       }

View Code

#include <iostream>
using namespace std;
int n,m, a[10];
void DFS(int k)
{   if (k>n)
    { for (int i=1; i<=n; i++)

       cout<<a[i]<<" ";
       cout<<endl;
    }
    else
       for (int i=0; i<=1; i++)
       {    a[k]=i;    DFS(k+1);      }
}
int main()
{        cin>>n;         DFS(1);    return 0;       }

********************************************************************************************************************

***************************************************************************************************************************

#include <iostream>
using namespace std;
int n,m, a[10];
void DFS(int k)
{   if (k==n)
    { for (int i=0; i<n; i++)
       if (a[i]==1) cout<<i+1<<" ";
       cout<<endl;
    }
    else
       for (int i=1; i<=2; i++)
       {    a[k]=i;    DFS(k+1);      }
}
int main()
{        cin>>n;         DFS(0);    return 0;       }

#include <iostream>
using namespace std;
int n,m, a[10];
void DFS(int k)
{   if (k==n)
    { for (int i=0; i<n; i++)
       if (a[i]==0) cout<<i+1<<" ";
       cout<<endl;
    }
    else
       for (int i=0; i<=1; i++)
       {    a[k]=i;    DFS(k+1);      }
}
int main()
{        cin>>n;         DFS(0);    return 0;       }

// 子集问题   dfs代码2
#include <iostream>
using namespace std;
int n,m, a[10];
void DFS(int k)
{   if (k==n)
    { for (int i=0; i<n; i++)
       if (a[i]==1) cout<<i+1<<" ";
       cout<<endl;
    }
    else
       for (int i=0; i<=1; i++)
       {    a[k]=i;    DFS(k+1);      }
}
int main()
{        cin>>n;         DFS(0);    return 0;       }

******************************************************************************************************************************************

#include <iostream>
using namespace std;
int n;
int main()
{   int i,j;
    cin>>n;
    for (i=0; i<(1<<n); i++)
    {
    for (j=0;j<n;j++)
           if ( i&(1<<j)) cout<<j<<" ";
        cout<<endl;
    }
    return 0;
}

// 子集问题二进制转换法

#include <iostream>

using namespace std;

int n;

int main()

{ int i,j;

cin>>n;

for (i=0; i<(1<<n); i++)

{

for (j=0;j<n;j++)

if ( i & (1<<j) ) cout<<j+1<<" ";

cout<<endl;

}

return 0;

}

DFS（ 修改）

DFS（修改）