78. Subsets

늘보·2021년 11월 1일

LeetCode

목록 보기

65/69

💡 풀이

var subsets = function (nums) {
  let result = [[]];

  function backtrack(first, stack) {
    for (let i = first; i < nums.length; i++) {
      stack.push(nums[i]);
      result.push([...stack]);
      backtrack(i + 1, stack);
      stack.pop();
    }
  }

  backtrack(0, []);
  return result;
};

let nums = [1, 2, 3];
console.log(subsets(nums));

📝 결과

📝 정리

이전과 비슷하게 BackTracking의 기초가 되는 문제다. 문제에는 중복이 되지 않는 배열인 nums 배열이 있는데, 요구사항은 모든 subset을 return하는 문제다. (=subarray) BackTracking 알고리즘이 작동하는 원리를 알고있다면 이해하기 쉬울 것이다. (아직 나도 완전히 이해된건 아니다)

풀이는 다음과 같다.

정답을 담을 2차원 배열 result=[[]]를 선언해준다.
backtrack이라는 재귀적으로 작동할 함수를 선언해준다.
함수 안에 first, 즉 backTrack 함수의 첫 번째 파라미터부터 nums 배열의 길이까지 반복문을 돌린다.
이후 stack이라는 임의의 배열에 nums 배열의 요소를 담는다.
그리고 stack 배열을 복사해서 result 배열에 넣어준다.
다시 재귀적으로 함수를 호출하고(다른 경우 탐색을 위해), 이후 stack 배열에 담겼던 요소를 pop을 통해 제거해준다. (BactTrack이 작동하는 부분)