C# [백준 BAEKJOON] 1182번 부분수열의 합

문제

N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

 

출력

첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.

 

1182번: 부분수열의 합

 

 

풀이 코드

using System;

class Program
{
    static void Main(string[] args)
    {
        var input = Console.ReadLine().Split();
        var num1 = Int32.Parse(input[0]);
        var num2 = Int32.Parse(input[1]);

        var input2 = Console.ReadLine().Split();

        var indexArray = new int[num1];
        var array = new int[num1];
        var result = 0;

        for (int i = 0; i < num1; i++)
        {
            array[i] = Int32.Parse(input2[i]);
        }

        for (int i = 1; i < array.Length + 1; i++)
        {
            Combination_DFS(indexArray, array, 0, 0, i, num2, ref result);
        }

        Console.WriteLine(result);
    }

    static void Combination_DFS(int[] array, int[] newArray, int now, int pos, int r, int sum, ref int result)
    {
        if (now == r)
        {
            int total = 0;

            for (int i = 0; i < r; i++)
            {
                total += newArray[array[i]];
            }

            if (total == sum)
            {
                result++;
            }

            return;
        }

        for (int idx = pos; idx < array.Length; idx++)
        {
            array[now] = idx;
            Combination_DFS(array, newArray, now + 1, idx + 1, r, sum, ref result);
        }
    }
}

 

 

0을 입력하는 경우에 대한 예외처리를 잘하자. 보통 해당 부분에서 많이 틀린다.