IF - 순열

문제

예시

Input	Input	Output
[3,6,9]	2	[ [ 3, 6 ], [ 3, 9 ], [ 6, 3 ], [ 6, 9 ], [ 9, 3 ], [ 9, 6 ] ]

풀이 및 회고

• 알고리즘 문제에 자주 나오는 순열을 구하는 문제이다.
• 각 DFS 마다 출력할 수의 조합을 담을 배열 tmp 와 tmp에 값을 넣어도 될지 판별할 check 배열을 선언한다.
• DFS의 종료조건은 깊이가 M과 같을 때 이며, 이 때 tmp 배열의 복사본을 출력한다.
• 종료조건 외에는 주어진 배열 numbers 를 순회하면서 check[i] 가 0일 때 만 tmp[L] 에 numbers[i] 를 할당한다.
• 이후 DFS 로 깊이를 늘리고 다시 check[i] 를 0으로 바꾸면, 체크배열의 i번째 인덱스가 0일 때만 numbers의 i 번째 원소가 tmp의 원소가 될 수 있다.
• DFS에서 빠져나온 다음에는 다시 check배열의 i번째 인덱스를 0으로 바꿔놓는다.
• 어찌저찌 풀기는 했는데 다시 코드를 봐도 뭔가 오락가락 한다..

코드

const solution = (numbers, M) => {
	const answer = [];
	const check = new Array(numbers.length);
	check.fill(0);
	const tmp = new Array(M);
	tmp.fill(0);

	const DFS = (L) => {
		if (L === M) {
			answer.push([...tmp]);
		} else {
			for (let i = 0; i < numbers.length; i++) {
				if (check[i] === 0) {
					check[i] = 1;
					tmp[L] = numbers[i];
					DFS(L + 1);
					check[i] = 0;
				}
			}
		}
	};
	DFS(0);
	console.log(answer);
};