순열

순열은 서로 다른 n개의 원소에서 r개를 중복없이 순서에 상관있게 선택하는 혹은 나열하는 것이다. 예시로 [1,2,3] 배열에서 2개를 선택해 만든 순열은 아래와 같다.

[1,2]
[1,3]
[2,1]
[2,3]
[3,1]
[3,2]

방문 표시를 이용해 백트래킹으로 구현

1. 배열 [1,2,3] 중 2개의 원소를 뽑아 순열을 만들어보자
   아래 코드에서 arr는 [1,2,3], k는 2이다
   k는 현재 순열의 길이(채워진 원소 개수)를 나타낸다

2. 순열을 저장할 배열 perm의 각 원소의 값을 0으로 초기화해준다.
   백트래킹을 진행하면서 각 원소의 값을 업데이트해줄 것이다.

3. 초기화한 perm에 대해 백트래킹을 진행하자
   idx는 사용할 수 있는 arr 원소의 idx 범위를 나타낸다
   idx를 기준으로 for loop를 돌리면서 각 원소 값을 업데이트 시키며 백트래킹 진행
   이미 방문한 원소를 다시 방문하지 않도록 백트래킹 전에 visited 값을 true로 한 다음 백트래킹 후 다시 false로 변경해주기 (다음 상태에서 해당 원소를 사용 x)

4. 만약 idx가 k와 같아지게 된다면 순열 완성
   따라서 해당 순열을 answer에 push하고 리턴한다
   리턴을 하게 되면 이전 상태로 돌아가게 된다
   백트래킹을 종료하면 해당 원소에 대해 visited를 true로 변경해 다시 해당 원소를 사용할 수 있게 하기

5. 백트래킹이 전부 종료되면 answer에 원소를 두 개 뽑아 만든 순열 [ 1, 2 ], [ 1, 3 ], [ 2, 1 ], [ 2, 3 ], [ 3, 1 ], [ 3, 2 ] 이 들어가 있다.

function permute(arr, k) {
    const perm = [...Array(k)].fill(0); // 순열
    const visited = [...Array(arr.length)].fill(false); // 방문처리
    const answer = []; // 만들어진 순열들 저장
    backTracking(answer, perm, arr, visited, 0, k); // 백트래킹
    return answer;
}

// 백트래킹
function backTracking(answer, perm, arr, visited, idx, k) {
    // 순열 완성 (원소들이 전부 채워지면)
    if (idx === k) {
        answer.push([...perm]);
        return;
    }
    // 순열이 아직 완성 안 되었다면
    for (let i=0; i<arr.length; i++) {
        if (visited[i]) continue; // 방문한 원소면 continue
        perm[idx] = arr[i];
        visited[i] = true;
        backTracking(answer, perm, arr, visited, idx+1, k);
        visited[i] = false;
    }
}

// [ [ 1, 2 ], [ 1, 3 ], [ 2, 1 ], [ 2, 3 ], [ 3, 1 ], [ 3, 2 ] ]
console.log(permute([1,2,3], 2));