DFS (순열, 조합)

조합 

조합은 전의 요소는 다시는 쳐다도 안본다는 것이 중요

#include <iostream>
#include <vector>

using namespace std;

// 조합
// 123 !=  213 

int Arr[10] = {0,1,2,3,4,5,6,7,8,9};
bool Select[10];


void DFS(int Idx, int Cnt, int target_num)
{
    if (Cnt == target_num)
    {
        for (int i=0; i<10; i++) 
            if (Select[i])
                printf("%d ", Arr[i]);
        printf("\n");
        return;
    }
 
    for (int i = Idx; i < 10; i++)
    {
        if (Select[i] == true) continue;
        Select[i] = true;

        DFS(i, Cnt + 1, target_num);
        Select[i] = false;
    }
}

int main(void)
{

    int target_num;
    scanf("%d", &target_num);

    DFS(0, 0, target_num);
}

순열

#include <vector>
#include <algorithm>

sort(v.begin(), v.end());
do {
	for(int i=0; i<v.size(); i++)
		// do smt

}while (next_permutation(v.begin(), v.end()));

-----------------------------
#include <iostream>
#include <vector>

using namespace std;

// 순열
// 123 ==  213 

int Arr[10] = {0,1,2,3,4,5,6,7,8,9};
bool Select[10];
vector <int> v;
int answer;

void DFS(int Cnt, int target_num)
{
    if (Cnt == target_num)
    {
        answer += 1;
        for (int i=0; i<v.size(); i++) 
            printf("%d ", v[i]);
        printf("\n");
        return;
    }
 
    for (int i = 0; i < 10; i++)
    {
        if (Select[i] == true) continue;
        Select[i] = true;
        v.push_back(Arr[i]);
        DFS(Cnt + 1, target_num);
        Select[i] = false;
        v.pop_back();
    }
}

int main(void)
{

    int target_num;
    scanf("%d", &target_num);

    DFS(0, target_num);

    printf("answer: %d\n", answer);
}