[백준 1182] 부분수열의 합 (C++/Python)

C++)

#include <iostream>
#include <algorithm>
#define MAX_NUM 22
using namespace std;

int n;
int s;
int ans;
int arr[MAX_NUM];
bool visited[MAX_NUM];

void suyeol(int cnt, int sum, int start) {
	if (cnt > 0 && sum == s)
		ans++;

	for (int i = start; i < n; i++) {
		if (!visited[i]) {
			visited[i] = true;
			suyeol(cnt + 1, sum + arr[i], i+1);
			visited[i] = false;
		}
	}
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> n >> s;

	for (int i = 0; i < n; i++)
		cin >> arr[i];

	suyeol(0, 0, 0);

	cout << ans;

	return 0; 
}

 

 

 

Python)

import sys

read = sys.stdin.readline

n, s = map(int, read().rstrip().split())
arr = list(map(int, read().rstrip().split()))
visited = [False] * n
ans = 0

def suyeol(cnt, sum, cur):
    global ans
    if cnt > 0 and sum == s:
        ans += 1

    for i in range(cur, n):
        if not visited[i]:
            visited[i] = True
            suyeol(cnt+1, sum + arr[i], i+1)
            visited[i] = False
    
suyeol(0, 0, 0)

print(ans)