[백준][1182] 부분수열의 합

• 문제
  • 1182번: 부분수열의 합
• 해설

  • import sys
    
    int_cnt, target_sum = [int(x) for x in sys.stdin.readline().split()]
    
    given_seq = [int(x) for x in sys.stdin.readline().split()]
    
    
    def go(seq, cur_sum, cur_ind, used_inds):
        res = 0
    
        # 정답
        if cur_sum == target_sum and cur_ind == len(seq) and used_inds:
            return 1
    
        # 불가능
        if cur_ind == len(seq):
            return 0
    
        if cur_ind < len(seq):
            # 현재 idx를 사용한 경우
            res += go(seq, cur_sum + seq[cur_ind], cur_ind + 1, used_inds + [cur_ind])
            # 현재 idx를 사용하지 않은 경우
            res += go(seq, cur_sum, cur_ind + 1, used_inds)
    
        return res
    
    
    print(go(given_seq, 0, 0, []))

• 포인트
  • BruteForce임을 눈치챈다.
  • 첫 원소가 포함될 때 안될 때, 각 경우마다 두번째 원소가 포함될 떄 안될 때, ... 재귀 구현