Javascript 알고리즘: 역추적

반응형

가능한 모든 조합 또는 일부 제약 조건이 있는 조합을 찾는 작업이라면 역추적 문제일 가능성이 높습니다. 이런 유형의 질문들이 제가 고민하던 것들이기 때문에 여기서 그것들을 세분화하려고 합니다.

46. 순열.

고유한 정수의 배열 번호가 지정되면 가능한 모든 순열을 반환합니다. 답변은 어떤 순서로든 반환할 수 있습니다.

 

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

이것의 역추적 솔루션은 매우 유사하며, 단지 우리가 다음 반복으로 전달할 배열의 조건과 방법을 달리 할 뿐이다. 이 경우 현재를 제외한 모든 요소를 통과시켜야 합니다.

이 솔루션의 시간 복잡도는 O(n!)입니다. 가능한 모든 솔루션을 검토하고 있으며 n!개의 솔루션이 있습니다.

역추적 작업에 대한 일반적인 접근 방식

backtrack() {
      if (GOAL_REACHED) {
                addSolutionToRes
      } else {
                for (var i = 0; i < NUMBER_OF_CHOICES; i++) {
                              addItem
                                          backtrack()
                              removeItem
                }
      }
}

 

47. 순열 II

중복 항목이 포함될 수 있는 숫자와 숫자의 집합이 지정되면 가능한 모든 고유 순열을 순서에 상관없이 반환합니다.

Input: nums = [1,1,2]
Output:
[[1,1,2], [1,2,1], [2,1,1]]

기존과 거의 동일한 솔루션이며, 중복 여부를 확인하기 위해 결과를 객체로 저장하기만 합니다.

78. 부분 집합.

 

고유한 요소의 정수 배열 숫자가 지정되면 가능한 모든 하위 집합(전원 집합)을 반환합니다. 솔루션 세트에는 중복된 하위 집합이 없어야 합니다. 어떤 순서로든 용액을 반환하십시오.

Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

해결책

가능한 모든 부분 집합으로 트리를 만들자.

 

DFS처럼 보이므로 두 개의 매개 변수를 사용하여 재귀 함수를 정의해보자.

• nums — 각 단계에서 추가할 수 있는 사용 가능한 숫자의 배열
• 경로 — 현재 조합

각 반복 시 현재 경로를 결과 어레이에 추가한 다음 남은 숫자(숫자)

90번 부분 집합 II

중복을 포함할 수 있는 정수 배열 숫자가 지정되면 가능한 모든 하위 집합(전원 집합)을 반환합니다. 솔루션 세트에는 중복된 하위 집합이 없어야 합니다. 어떤 순서로든 용액을 반환하십시오.

 

Input: nums = [1,2,2]
Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]

이 작업은 이전 작업과 거의 동일하지만, 우리는 한 가지 제약을 추가하고 있습니다. 중복을 피하기 위해 먼저 배열을 정렬한 다음 현재 요소가 이전 요소와 동일하지 않은지 확인해야 합니다.

22. 괄호 생성

괄호 쌍이 n개 주어지면 올바른 형식의 괄호의 모든 조합을 생성하는 함수를 작성한다.

 

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]