[LeetCode] 78 Subsets JavaScript

문제 링크

Subsets - LeetCode

 

문제 유형

백트래킹(Backtracking)

 

문제 풀이

해당 문제는 중복되지 않는 숫자들로 이루어진 배열이 주어지고, 이 숫자들로 만들 수 있는 부분집합을 배열로 반환하는 문제이다.

가능한 후보들을 모두 탐색해야 부분집합을 구할 수 있기에 가능한 후보들을 찾다가 조건을 만족하지 않으면 다시 되돌아가는 백트래킹 방식을 사용할 수 있다.

 

해당 문제가 재귀적으로 어떻게 동작하는지 자세히 살펴보자.

• 각 원소는 각 원소가 집합의 원소인 경우와 집합의 원소가 아닌 경우(∅)로 나뉜다. 런타임 시 backTracking 함수가 호출되고 call stack에 push된다.
  재귀 종료 조건을 만족하는지 검사하고 재귀 종료 조건을 만족하지 않으면 다음 레벨을 탐색하기 위한 함수를 호출한다.
  현재 0 레벨에서는 1이라는 원소가 집합의 원소인 경우와 아닌 경우로 나뉜다.
  1번은 1이 집합의 원소일 때 다음 탐색을 진행하기 위한 호출이고, 2번은 1이 집합의 원소가 아닐 때 다음 탐색을 진행하기 위한 호출이다. 1번 함수가 먼저 호출되어 call stack에 push되고, 인자를 받아 함수가 실행된다.

nums = [1, 2, 3]

• 인자로 인덱스 1, 배열 [1]을 갖는 함수가 실행된다. 재귀 종료 조건을 만족하지 않으므로 backTracking(2, [1, 2]) 함수가 호출되고 call stack에 push된다.

• 인자로 인덱스 2, 배열 [1, 2]를 갖는 함수가 실행된다. 재귀 종료 조건을 만족하지 않으므로 backTracking(3, [1, 2, 3]) 함수가 호출되고 call stack에 push된다.

• 인자로 인덱스 3, 배열 [1, 2, 3]를 갖는 함수가 실행된다. 재귀 종료 조건을 만족하므로 결과를 담는 subsets 배열에 [1, 2, 3]을 부분집합으로 추가하고 해당 함수를 리턴해 종료한다. backTracking(3, [1, 2, 3])이 call stack에서 pop된다.

• 인자 인덱스 3, 배열 [1, 2]를 갖는 함수 2가 실행된다. 재귀 종료 조건을 만족하지 않으므로 backTracking(3,  [1, 2]) 함수가 호출되고 call stack에 push된다.

• 인자로 인덱스 3, 배열 [1, 2]를 갖는 함수가 실행된다. 재귀 종료 조건을 만족하므로 결과를 담는 subsets 배열에 [1, 2]을 부분집합으로 추가하고 해당 함수를 리턴해 종료한다. backTracking(3, [1, 2])이 call stack에서 pop된다. backTracking(2, [1, 2])도 종료되어 call stack에서 pop된다. backTracking(2, [1]) 함수가 호출되고 call stack에 push된다.인자로 인덱스 2, 배열 [1]를 갖는 함수가 실행된다. 재귀 종료 조건을 만족하지 않으므로 backTracking(2, [1]) 함수가 호출되고 call stack에 push된다.

• 인자로 인덱스 2, 배열 [1]를 갖는 함수가 실행된다. 재귀 종료 조건을 만족하지 않으므로 backTracking(3, [1, 3]) 함수가 호출되고 call stack에 push된다.

• 인자로 인덱스 3, 배열 [1, 3]을 갖는 함수가 실행된다. 재귀 종료 조건을 만족하므로 결과를 담는 subsets 배열에 [1, 3]을 부분집합으로 추가하고 해당 함수를 리턴해 종료한다. backTracking(3, [1, 3])은 call stack에서 pop된다. 인자로 인덱스 3, 배열 [1]을 갖는 함수가 호출되고 call stack에 push된다.

위와 같이 가장 깊은 레벨까지 탐색해 더 이상의 레벨을 탐색할 수 없을 때 한 레벨씩 거슬러 올라와 다른 후보를 탐색하는 과정을 통해 부분집합을 구할 수 있다.

 

코드

const subsets = (nums) => {
    const subsets = [];
    
    const backTracking = (i, arr) => {
        if (i === nums.length) {
            subsets.push(arr);
            return;
        }
        backTracking(i + 1, [...arr, nums[i]]); // 1번
        backTracking(i + 1, arr); // 2번
    }
    
    backTracking(0, []);
    return subsets;
};

 

참고

https://www.youtube.com/watch?v=gVijWUHWzAU