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

순열 생성

서로 다른 정수 배열 nums가 주어져요. nums의 원소를 모두 써서 만들 수 있는 모든 순열을 담은 배열을 반환해요. 순열은 n!개예요.

부분집합·조합과 달리, 순열은 매번 처음부터 모든 원소를 후보로 보되 이미 쓴 원소만 막아요. used 배열로 어떤 원소를 이미 골랐는지 표시해요.

순열들의 순서는 신경 쓰지 않지만, 각 순열 안 원소의 순서는 의미가 있어요. [1, 2, 3]과 [3, 2, 1]은 서로 다른 순열이에요.

예시

예시 1
입력
nums = [1, 2, 3]
출력
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
설명
순열 6개예요. 바깥 순서는 달라도 괜찮아요.
예시 2
입력
nums = [0, 1]
출력
[[0, 1], [1, 0]]

제한 사항

  • 1 ≤ nums.length ≤ 8
  • nums의 값은 서로 달라요.
  • -1,000 ≤ nums[i] ≤ 1,000
path의 길이가 nums.length가 되면 완성된 순열이니 복사본을 담아요. 아니면 모든 원소를 훑되 used[i]가 참이면 건너뛰고, 아니면 표시한 뒤 넣고 재귀하고, 돌아와서 표시와 원소를 함께 되돌려요.
javascript
function permutations(nums) {
  const out = [];
  const path = [];
  const used = new Array(nums.length).fill(false);
  function backtrack() {
    if (path.length === nums.length) {
      out.push([...path]);
      return;
    }
    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue;
      used[i] = true;
      path.push(nums[i]);
      backtrack();
      path.pop();
      used[i] = false;
    }
  }
  backtrack();
  return out;
}
이전 문제부분집합 모두 구하기
다음 문제합이 target인 조합
에디터를 불러오고 있어요…
코드를 작성하고를 눌러 예시 테스트를 확인해 보세요.