C# 백준 1182 부분수열의 합(백트래킹, 브루트포스)

1182번: 부분수열의 합

IDEA

공집합을 제외한 모든 부분 집합의 원소의 합을 계산해보는 문제다. 하나만 고르는 경우, 둘을 고르는 경우, 이렇게 따로따로 생각하면 어떻게 접근해야할지 좀 막막한데 백트래킹의 원리를 생각해보면 모든 경로를 탐색하고, 매 탐색마다 탐색 중인 정점의 수치를 더해주고 되돌아갈 때 더했던 값을 다시 빼주면 1~N개까지의 원소를 갖는 모든 부분 집합을 한번씩 탐색할 수 있다.

 

CODE

using System;
class Program
{
    static int N, S, sum, count;
    static int[] arr = new int[20];
    static void Main()
    {
        var ns = Console.ReadLine().Split();
        N = int.Parse(ns[0]); S = int.Parse(ns[1]);
        var n = Console.ReadLine().Split();
        for (int i = 0; i < N; i++)
            arr[i] = int.Parse(n[i]);
        for(int i = 0; i < N; i++) Tracking(i);
        // 출발 지점을 0~N까지 모두 탐색해본다.
        Console.WriteLine(count);
    }
    static void Tracking(int index)
    {
        sum += arr[index];
        // 이 지점의 값을 더한다.
        
        if (S == sum) count++;
        // 만약 S와 더한 값이 같다면 현재 탐색한 지점들을 원소로하는
        // 부분집합은 그 합이 S와 같다.
        
        for (int i = index + 1; i < N; i++)
            Tracking(i);
            // 다음 칸부터 재귀해서 탐색 한다.
            
        sum -= arr[index];
        // 탐색이 끝나고 되돌아갈 때 이 지점의 값을 다시 빼준다.
    }
}