[c++] 조합, 순열, 중복조합, 중복순열 (DFS)

정보 출처

https://yabmoons.tistory.com/99

조합

int arr[5];
bool selected[5];

void dfs(int idx, int cnt) {
	if(cnt == 3) {
    	for(int i=0; i<5; i++) {
            if(selected[i]) {
            	cout << arr[i] << ' ';
            }
        }
        cout << endl;
    }
    else {
    	for(int i=idx, i<5; i++) {
        	if(selected[i]) continue;
            selectes[i] = true;
            dfs(i, cnt+1);
            selected[i] = false;
        }
    }
}

순열

int arr[5];
bool selected[5];
vector<int> v;

void dfs(int cnt) {
	if(cnt == 3) { // 3개를 뽑는다면
		for(int i=0; i<5; i++) {
    		cout << v[i] << ' ';
        }
        cout << endl;
    }
    else {
    	for(int i=0, i<5; i++) {
        	if(selected[i]) continue;
            selected[i] = true;
            v.push_back(arr[i]);
            dfs(cnt+1);
            v.pop_back();
            selected[i] = false;
        }
    }
}

중복조합

int arr[5];
int selected[5];

void dfs(int idx, int cnt) {
	if(cnt == 3) {
    	for(int i=0; i<3; i++) {
        	cout << selected[i] << ' ';
        }
        cout << endl;
    }
    else {
    	for(int i=idx; i<5; i++) {
        	selected[cnt] = arr[i];
            dfs(i, cnt+1);
        }
    }
}

중복순열

int arr[5];
int selected[5];

void dfs(int cnt) {
	if(cnt == 3) {
    	for(int i=0; i<3; i++) {
        	cout << selected[i] << ' ';
        }
        cout << endl;
    }
    else {
    	for(int i=0; i<5; i++) {
        	selected[cnt] = arr[i];
            dfs(cnt+1);
        }
    }
}