[알고리즘] 순열

순열 로직 설명 들어가기 전에..

JS spread 연산자(...): 기존 배열이나 객체의 전체 또는 일부를 다른 배열이나 객체로 복사

ES6 JavaScript Spread 연산자 (...)

const fruitAll = [...fruitOne, ...fruitTwo];

console.log(fruitAll); // ['apple', 'banana', 'grape', 'peach']

• 이처럼 기존에 생성되어 변수에 할당되어 있는 배열이나 객체를 새로운 변수에 할당하게 되면, 새로운 변수는 기존의 변수에 할당되어 있는 객체 또는 배열을 참조한다.

• 원본의 값을 변경시키지 않고, 복사한 객체의 프로퍼티 값만 변경하는 방법이다. → 얕은 복사

• 깊은 복사를 구현하기 위해서는, 1)for문으로 재귀적인 깊은 복사 구현, 2)JSON으로 stringfy시킨 후 parse 거치기, 3) lodash 라이브러리 사용...

• 참조가 아닌 복사를 하기 위해서 ES5에서는 slice 또는 map을 활용하여 배열을 복사함

// slice 사용
const fruitOne = ['apple', 'banana'];
const fruitTwo = fruitOne.slice();

const fruitTwo.push('grape');

console.log(fruitOne); // ['apple', 'banana']
console.log(fruitTwo); // ['apple', 'banana', 'grape']


// map 사용
const fruitOne = ['apple', 'banana'];
const fruitTwo = fruitOne.map((item) => item);

const fruitTwo.push('grape');

console.log(fruitOne); // ['apple', 'banana']
console.log(fruitTwo); // ['apple', 'banana', 'grape']

// spread 연산자 사용
const fruitOne = ['apple', 'banana'];
const fruitTwo = [...fruitOne, 'grape'];

console.log(fruitOne); // ['apple', 'banana']
console.log(fruitTwo); // ['apple', 'banana', 'grape']

선택한 값: picked
선택하지 않은 값: unpicked

재귀 함수 호출을 통해 값들 관리 - 조건문 걸기

if,
배열 내 모든 값들이 선택되었을 때, 정답을 새로운 배열 permutations에 추가해준다. (재귀 함수 호출 중단 조건)

else,
남은 값들이 없을 때까지 반복해준다.(forEach: 배열과 인덱스 모두 필요)

• 내부에 재귀 함수 호출
• 재귀 함수 내 첫번째 인자 == unpicked에 있는 값을 새롭게 선택함
  재귀 함수 내 두번째 인자 == num(새롭게 선택된 값)을 제외한 배열 → slice(i 이전 모든 값들, i 다음의 모든 값들)

function permute(nums: number[]): number[][] {
  const permutations = [];

  const dfs = (picked, unpicked) => {
    if (!unpicked.length) return permutations.push(picked);

    unpicked.forEach((num, i) =>
      dfs(
        [...picked, num],
        [...unpicked.slice(0, i), ...unpicked.slice(i + 1)],
      ),
    );
  };

  dfs([], nums);

  return permutations;
}

참고 자료:
https://www.youtube.com/watch?v=YcP8hnaBWtM
https://www.algodale.com/problems/permutations/
https://velog.io/@tnstjd120/%EC%8A%A4%ED%94%84%EB%A0%88%EB%93%9C-%EC%97%B0%EC%82%B0%EC%9E%90spread-operator
https://velog.io/@yukyung/Spread-Operator%EB%8A%94-%EC%96%95%EC%9D%80-%EB%B3%B5%EC%82%AC%EC%9D%BC%EA%B9%8C-%EA%B9%8A%EC%9D%80-%EB%B3%B5%EC%82%AC%EC%9D%BC%EA%B9%8C