input = [1, 2, 3, 4, 5]의 값이 주어졌고 해당 배열로 만들 수 있는 배열의 길이가 2인 배열들을 요구할 경우가 있다. 이 문제의 경우 주어지는 배열의 모든 값을 탐색해야 한다. 이 문제의 해결 방법을 간단하게 설명해보겠다.[1]로 시작하는 값 뒤에 올 수 있는 값들인 [2], [3], [4], [5]들을 이용하여 배열의 길이가 2인 정답을 나열해보자는 것이다.start = i + 1을 통해 input 배열을 줄이지 않고 i = 0부터 시작하여 모두 사용한다는 점이 다른 점이다.function backtracking(input, target) {
const answer = [];
dfs(0, []);
return answer;
function dfs(start, curr) {
if (start >= input.length) {
return;
}
if (curr.length === target) {
answer.push([...curr]);
return;
}
for (let i = start; i < input.length; i++) {
curr.push(input[i]);
curr.pop();
}
}
}
backtracking([1, 2, 3, 4, 5], 2);
const input = [1, 2, 3, 4, 5];
const answer: number[][] = [];
function backtracking(curr: number[], visit: boolean[]) {
if (curr.length === input.length) {
answer.push([...curr]);
return;
}
for (let i = 0; i < input.length; i++) {
if (visit[i]) continue;
curr.push(input[i]);
visit[i] = true;
backtracking(curr, visit);
curr.pop();
visit[i] = false;
}
}