귀착 과 추이 총 결

 
1.Acwing 92  순환 실현 지수 형 매 거
1 ~ n 이 n 개의 정수 에서 무 작위 로 여러 개 를 선택 하여 가능 한 모든 선택 방안 을 출력 합 니 다.
입력 형식
정수 n 을 입력 하 십시오.
출력 형식
줄 마다 하나의 방안 을 출력 합 니 다.
같은 줄 안의 수 는 반드시 오름차 순 으로 배열 해 야 하 며, 인접 한 두 수 는 마침 한 개의 빈 칸 으로 분리 해 야 한다.
어떤 숫자 를 선택 하지 않 은 방안 에 대해 서 는 빈 줄 을 출력 합 니 다.
이 문 제 는 사용자 정의 검사 기 (SPJ) 가 있 으 며, 각 줄 (프로젝트 별) 간 의 순서 가 임 의 입 니 다.
데이터 범위
1≤n≤151≤n≤15
입력 예시:

3

출력 예시:

3
2
2 3
1
1 3
1 2
1 2 3

 

/*
            ，           ，          2^n  ，  dfs           
   ，                   。
*/
#include

using namespace std;

int n;

void dfs(int u,int state){
    if(u == n){
        for(int i = 0 ; i < n ;i++){
            if(state >> i & 1){//  state   i     1 
                cout << i + 1 << ' ';
            }
        }
        cout << endl;
        return ;
    }
    dfs(u+1,state);//      
    dfs(u + 1, state | 1 << u);//     
}

int main(){
    cin >> n;
    dfs(0,0);
    return 0;
}

 
2.Acwing 93  귀속 실현 조합 형 매 거
1 ~ n 이 n 개의 정수 중에서 m 개 를 무 작위 로 선택 하여 가능 한 모든 선택 방안 을 출력 합 니 다.
입력 형식
두 정수 n,mn,m ,같은 줄 에서 빈 칸 으로 나누다.
출력 형식
모든 방안 을 줄 당 1 개 씩 작은 것 부터 큰 것 까지 순서대로 출력 합 니 다.
우선, 같은 줄 안의 수 는 오름차 순 으로 배열 되 고 인접 한 두 수 는 하나의 빈 칸 으로 분리 된다.
그 다음으로 두 개의 서로 다른 줄 에 대해 아래 표 시 된 숫자 를 일일이 비교 하면 사전 순서 가 비교적 작은 것 이 앞 에 있다 (예 를 들 어 1, 3, 5, 7 은 1, 3, 6, 8 앞 에 있다).
데이터 범위
n>0n>0 , 0≤m≤n0≤m≤n , n+(n−m)≤25n+(n−m)≤25
입력 예시:

5 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 
#include 
#include 

using namespace std;

int n, m;

void dfs(int u, int s, int state)//  s     
{
    if (s == m)
    {
        for (int i = 0; i < n; i ++ )
            if (state >> i & 1)
                cout << i + 1 << ' ';
        cout << endl;
        return;
    }
    if (u == n) return;

    for (int i = u; i < n; i ++ )
    {
        dfs(i + 1, s + 1, state + (1 << i));//    ，    2^n，   dfs      
    }
}

int main()
{
    cin >> n >> m;
    dfs(0, 0, 0);
    return 0;
}

3. Acwing 94  재 귀 는 배열 형 매 거 를 실현 한다.
1 ~ nn 을 이. nn 하나의 정수 가 한 줄 로 늘 어선 후 무 작위 로 순 서 를 흐 트 러 뜨리 고 가능 한 모든 순 서 를 출력 합 니 다.
입력 형식
하나의 정수 n.
출력 형식
모든 방안 을 줄 당 1 개 씩 작은 것 부터 큰 것 까지 순서대로 출력 합 니 다.
우선 같은 줄 에 인접 한 두 개의 수 는 하나의 빈 칸 으로 분리 된다.
그 다음 에 두 개의 서로 다른 줄 에 대해 아래 표 시 된 숫자 를 일일이 비교 하면 사전 순서 가 비교적 작은 것 이 앞 에 있다.
데이터 범위
1≤n≤91≤n≤9
입력 예시:

3

출력 예시:

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

#include
#include
#include
#include

using namespace std;

int n;
vector path;

void dfs(int u,int state){
    if(u == n){
        for(auto x : path){
            cout << x << ' ';
        }
        cout << endl;
        return ;
    }
    for(int i = 0 ; i < n ;i++){
        if(!(state >> i & 1)){
            path.push_back(i + 1);
            dfs(u+1,state+(1<> n;
    dfs(0,0);
    return 0;
}