← 17주차 · 백트래킹
보통백트래킹

부분집합 모두 구하기

서로 다른 정수 배열 nums가 주어져요. nums의 모든 부분집합을 담은 배열을 반환해요. 빈 집합과 전체 집합도 포함해요.

원소마다 '넣는다 / 안 넣는다' 두 갈래가 있으니 부분집합은 2ⁿ개예요. 하나를 고르고, 더 깊이 들어가고, 돌아와서 그 선택을 되돌리는 백트래킹으로 빠짐없이 만들어요.

부분집합의 순서나 각 부분집합 안 원소의 순서는 채점에서 신경 쓰지 않아요.

예시

예시 1
입력
nums = [1, 2, 3]
출력
[[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]
설명
부분집합 8개예요. 순서는 달라도 괜찮아요.
예시 2
입력
nums = [0]
출력
[[], [0]]

제한 사항

  • 0 ≤ nums.length ≤ 12
  • nums의 값은 서로 달라요.
  • -1,000 ≤ nums[i] ≤ 1,000
backtrack(start)를 만들어요. 함수에 들어오면 지금까지 고른 path의 복사본을 결과에 담아요. 그다음 start부터 각 원소를 골라 path에 넣고 backtrack(i + 1)로 진행한 뒤, 돌아와서 pop으로 되돌려요.
javascript
function subsetsAll(nums) {
  const out = [];
  const path = [];
  function backtrack(start) {
    out.push([...path]);
    for (let i = start; i < nums.length; i++) {
      path.push(nums[i]);
      backtrack(i + 1);
      path.pop();
    }
  }
  backtrack(0);
  return out;
}
이전 문제벽 부수고 이동하기
다음 문제순열 생성
에디터를 불러오고 있어요…
코드를 작성하고를 눌러 예시 테스트를 확인해 보세요.