LeetCode 문제 풀이 -- 20200517 역 추적 알고리즘 편

역 추적 알고리즘
역 추적 알고리즘 의 사상 은 매우 간단 하지만 응용 은 매우 광범 위 하 다.전형 적 인 깊이 검색 DFS 외 에 도 실제 소프트웨어 개발 이나 수학 응용 장면 에서 역 추적 알고리즘 사상 을 많이 사용 했다.소프트웨어 개발 에서 정규 표현 식 의 일치, 컴 파일 원리 중의 문법 분석;수학 응용 에서 수 독, 8 황후 문제 등 은 모두 거 슬러 올 라 가 는 사상 으로 해결 할 수 있다.역 추적 알고리즘 은 한 그룹의 가능 한 해 에서 기 대 를 만족 시 키 는 해 를 찾 는 데 적합 하고 보통 재 귀 코드 로 실현 하기에 적합 하 다.그리고 역 추적 알고리즘 자체 에 대해 간단하게 말하자면 우리 가 선택 을 만 날 때마다 모든 상황 을 시도 하 는 것 이다.상황 A 를 먼저 시도 한 다음 선택 하지 않 은 상태 로 상 태 를 초기 화하 고 상황 B 를 다시 시도 합 니 다.
 리 트 코드 연습 문제 두 문제 보 시 죠.LeetCode 전송 문.
 
46 전열
 
중복 되 지 않 은 숫자의 서열 을 정 하고 가능 한 모든 배열 을 되 돌려 줍 니 다.
 
예시:
 
입력: [1, 2, 3] 출력: [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]]
이 문 제 는 전형 적 인 역 추적 알고리즘 으로 해결 하기에 적합 한 문제 이다.중학교 에서 배열 조합 을 배 울 때 바로 이런 생각 이 었 다. 먼저 1 로 시작 하 는 모든 결 과 를 배열 한 결과 [1, 2, 3], [1, 3, 2] 를 포함한다.그리고 2 로 시작 하 는 결 과 를 배열 하고 마지막 으로 3 이다.1 에 대한 모든 배열 이 계산 되 었 을 때 사실은 '역 추적' 이 발생 했다. 왜냐하면 우 리 는 또 1 위 에 있 는 숫자 를 선택해 야 하기 때문이다.이때 1 은 이미 선택 한 것 이기 때문에 숫자 시작 을 바 꾸 어 아래 의 결 과 를 계속 계산한다.
앞에서 언급 한 역 추적 알고리즘 은 재 귀 를 사용 하여 실현 하기에 매우 적합 하 다.재 귀 에 관 해 서 는 우선 재 귀 중지 조건 을 찾 은 다음 에 전달 공식 을 찾 아야 한다.이 문제 와 결합 하여 재 귀 중지 조건 은 특정한 배열 의 결과 의 결합 에서 Count 는 3 과 같다. (즉, 모든 숫자 가 이 배열 에 포함 되 어 있다)푸 시 공식 은...
배열 결과 (n 개의 숫자 포함, 1 < =  n < = 배열 길이) = 배열 결과 (n - 1 개의 숫자 포함)  + (정렬 결과 (n - 1) 에 포 함 된 숫자 를 제외 한 임의의 숫자)
코드

 1         public IListint>> Permute(int[] nums)
 2         {
 3             IListint>> result = new Listint>>();
 4             LinkedList<int> temp = new LinkedList<int>();
 5 
 6             backtrack(nums, temp, result);
 7 
 8             return result;
 9         }
10 
11         private void backtrack(int[] nums, LinkedList<int> temp, IListint>> result)
12         {
13             if (temp.Count == nums.Count())
14             {
15                 result.Add(new List<int>(temp));
16                 return;
17             }
18 
19             for (int i = 0; i < nums.Length; i++)
20             {
21                 if (temp.Contains(nums[i]))
22                     continue;
23 
24                 temp.AddLast(nums[i]);
25                 backtrack(nums, temp, result);
26                 temp.RemoveLast();
27             }
28         }

위 코드 에 서 는 링크 드 리스트 temp 에 주의 하 셔 야 합 니 다.여기 서 temp 을 사용 하여 이번에 찾 은 결과 중 어떤 숫자 가 배열 에 추가 되 었 는 지 기록 합 니 다.temp 의 숫자 개수 가 주어진 숫자 개수 와 같 으 면 재 귀 종료 조건 에 이 르 렀 음 을 설명 합 니 다.만약 temp 에 어떤 숫자 가 포함 되 어 있다 면, 제목 의 요 구 를 바탕 으로 한다 면, 우 리 는 그것 을 더 이상 배열 에 넣 지 말 아야 하기 때문에 직접 건 너 뛸 수 있다.그리고 같은 층 의 재 귀 내 에서 우리 가 temp 에 어떤 값 을 추가 하려 고 시도 한 후에 temp 에서 제거 해 야 합 니 다. 즉, '역 추적' 입 니 다.같은 층 의 다양한 선택 사이 에 서로 영향 을 주어 서 는 안 되 기 때문이다.
 
47. 전열 II
중 복 된 숫자 를 포함 할 수 있 는 시퀀스 를 지정 하고 중복 되 지 않 는 모든 배열 을 되 돌려 줍 니 다.
예시:
입력: [1, 1, 2] 출력: [1, 1, 2], [1, 2, 1], [2, 1, 1]]
이 문 제 는 첫 번 째 문제 와 유사 한데, 이번 에는 중복 숫자 를 허용 한 것 과 차이 가 있다.여기 서 역 추적 알고리즘 중의 중요 한 기 교 를 언급 하고 가 지 를 잘라 야 한다.가지치기 란 우리 가 결 과 를 완전히 얻 기 전에 조건 에 맞지 않 는 가 지 를 직접 뛰 어 넘 는 것 을 말한다.46 문 항 에서 우 리 는 3 개의 서로 다른 숫자의 모든 순서 별 배열 조합 이 모두 6 가지 라 는 것 을 볼 수 있다.만약 우리 가 46 문제 의 방식 으로 본 문 제 를 계산한다 면 중복 되 는 결 과 를 얻 을 수 있 을 것 이다.그렇다면 완전한 결 과 를 얻 기 전에 어떤 지점 이 중복 되 는 지 판단 할 방법 은 없 을 까?사실은 있 습 니 다. code 를 살 펴 보 겠 습 니 다.

 1 public class Solution {
 2         public IListint>> PermuteUnique(int[] nums)
 3         {
 4             IListint>> result = new Listint>>();
 5             LinkedList<int> temp = new LinkedList<int>();
 6 
 7             nums = nums.OrderBy(x => x).ToArray();
 8 
 9             bool[] flag = new bool[nums.Length];
10 
11             dfs2(0, nums.Length, flag.ToList(), nums, temp, result);
12 
13             return result;
14         }
15 
16         private void dfs2(int depth, int length, List<bool> flag, int[] nums, LinkedList<int> temp, IListint>> result)
17         {
18             if (depth == length)
19             {
20                 result.Add(new List<int>(temp));
21                 return;
22             }
23 
24             for (int i = 0; i < nums.Length; i++)
25             {
26                 if (flag[i])
27                     continue;
28 
29                 if (i > 0 && nums[i] == nums[i - 1] && flag[i - 1] == false)
30                 {
31                     continue;
32                 }
33 
34                 flag[i] = true;
35                 temp.AddLast(nums[i]);
36                 dfs2(depth + 1, length, flag, nums, temp, result);
37 
38                 temp.RemoveLast();
39                 flag[i] = false;
40             }
41         }
42 }

지난 문제 에 비해 여기 에는 두 가지 변화 가 있다.먼저 배열 을 정렬 한 다음 에 하나의 flag 배열 을 더 해서 특정한 위치 에 있 는 숫자 가 이미 사용 되 었 는 지 여 부 를 표시 합 니 다.같은 값 의 배열 색인 이 인접 해 있다 는 것 을 보증 할 수 있 기 때문에 배열 정렬 이 다음 처리 종 류 를 처리 하 는 것 이 중요 합 니 다.그리고 가 지 를 자 르 는 부분 에 대해 필 자 는 문자 에 의 해 명확 하 게 묘사 할 수 없다 고 느 꼈 습 니 다. 그리고 여러분 께 서 이곳 을 옮 겨 주 십시오. 큰 남자 의 칭찬 에 대한 해답, 전송 문.
응, 문 제 는 많이 연습 해 야 지. 조금 만 고치 면 느낌 차이 가 커.