코영방

https://www.acmicpc.net/problem/1182

#include 
#include <bits/stdc++.h>
using namespace std;
/*
부분수열의 합
*/
int a[10000]={0,};
int main()
{
    int n,s,i,k,sum=0,cnt=0;
    scanf("%d %d",&n,&s);
    for(i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(i=1;i<(1<<n);i++){
        sum=0;
        for(k=0;k<n;k++)
        {
            if(i&(1<<k))
            {
                sum+=a[k+1];
            }
        }
        if(sum==s)
            cnt++;
    }
    printf("%d",cnt);
    return 0;
}

https://www.acmicpc.net/problem/15651

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. (중복가능)

N = 4, M = 2인 경우 아래와 같이 16(4*4) 개의 경우가 발생한다.

1 1
1 2
1 3
1 4
2 1
2 2
2 3
2 4
3 1
3 2
3 3
3 4
4 1
4 2
4 3
4 4

내 생각에는 N과 M(1)보다 풀이에 접근하기 더 쉬운 문제라고 생각한다. 내기준으로는 "N과 M(0)" 이 맞을듯.^^

#include <bits/stdc++.h>
using namespace std;
vector <int> res;
void NM3(int n, int m) {
    if (res.size() == m) {
        for (int i = 0; i < m; i++) {
            cout << res[i] << " ";
        }
        cout << '\n';
        return;
    }
    for (int i = 1; i <= n; i++) {
        res.push_back(i);
        NM3(n, m);
        res.pop_back();
    }
}
int main() {
    int n, m;
    cin >> n >> m;
    NM3(n, m);
    return 0;
}

https://www.acmicpc.net/problem/15650

N과 M(1)문제 풀이 참고바람. (https://coding-gongboo.tistory.com/9?category=829643)

N과 M(1) 과의 차이점은 "고른 수열은 오름차순이어야 한다"는 점이다.

이를 위해서 현재 선택된 수 보다 1개 높은 위치의 수를 부터 수열을 만들어 나가야 한다.

이를 위해서 NM2(재귀함수)에 start해야 할 위치를 인자로 넘겨주는 부분이 수정되었다.

그리고 항상 다음 수를 대상으로 수열을 만들어 나가기 때문에 중복체크를 위한 included배열은 필요없다.

#include <bits/stdc++.h>

using namespace std;
//bool included[10]; //중복 체크
vector <int> nm;
void NM2(int, int, int);

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

void NM2(int s, int n, int m) {
    if (nm.size() == m) {
        for (int i = 0; i < m; i++) {
            cout << nm[i] << " ";
        }
        cout << '\n';
        return;
    }
   
    for (int i = s; i <= n; i++) {
        //if (!included[i]) {
            //included[i] = true;
            nm.push_back(i);
            NM2(i + 1, n, m); //현재 nm vector에 넣은 수 이후 수를 확인 한다. (오름차순)
            nm.pop_back();
            //included[i] = false;
        //}
    }
}

두번째 풀이

각 수들을 포함 하거나 또는 포함 하지않으면서 다음수로 넘어가는 형태

#include <bits/stdc++.h>
using namespace std;
vector <int> nm;
void NM2(int level, int n, int m);

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

void NM2(int level, int n, int m) {
    if (nm.size() == m) {
        for (int i = 0; i < m; i++) {
            cout << nm[i] << " ";
        }
        cout << '\n';
        return;
    }
    if (level > n) return;
    nm.push_back(level);
    NM2(level + 1, n, m);
    nm.pop_back();
    NM2(level + 1, n, m);
}

세번째 풀이

배열을 사용해서 결과값을 저장한 위치에 해당하는 index 인자를 관리해주고,

오름차순을 위해 다음 수를 지정해주는 start를 관리해 주는 형태

#include <bits/stdc++.h>
using namespace std;
int res[10];
void go(int index, int start, int n, int m);

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

void go(int index, int start, int n, int m) {
    if (index == m) {
        for (int i = 0; i < m; i++) {
            cout << res[i];
            if (i != m - 1) cout << ' ';
        }
        cout << '\n';
        return;
    }
    for (int i = start; i <= n; i++) {
        res[index] = i;
        go(index + 1, i + 1, n, m);
    }
}