역 추적 알고리즘 상세 해석 및 Leetcode 고전 예제 풀이

무엇이 역 추적 법 입 니까?
프로 그래 밍 에서 상당 한 유형 이 한 조 의 해 를 구하 거나 모든 해 를 구하 거나 가장 좋 은 해 를 구 하 는 문제 가 있다. 예 를 들 어 독자 가 잘 아 는 8 황후 문 제 는 특정한 계산 법칙 에 따라 탐색 과 역 추적 의 검색 기술 로 해결 하 는 것 이다.역 추적 법 도 재 귀 과정 을 설계 하 는 중요 한 방법 이다. 그의 구 해 과정 은 실질 적 으로 '상태 나무' 를 먼저 옮 겨 다 니 는 과정 이다. 다만 이 나 무 는 옮 겨 다 니 기 전에 미리 만들어 진 것 이 아니 라 옮 겨 다 니 는 과정 에 담 겨 있다. -(엄 울 민) 우선, 어떤 문제 의 해 를 우 리 는 규칙 을 찾 아 계산 하기 어렵다. 공식 이 없 으 면 가능 한 모든 해 를 열거 할 수 밖 에 없다. 그리고 모든 해 가 우리 가 찾 는 조건 에 부합 되 는 지, 즉 흔히 말 하 는 것 이다.그리고 공간 을 푸 는 것 은 나무 모양 이 고 나무 가 옮 겨 다 니 는 것 이다.
그 다음 에 나무의 선착순, 즉 뿌리 는 먼저 검 사 를 받 았 고 이 진 트 리 의 선착순 은 뿌리, 왼쪽 나무, 오른쪽 나무의 순서 가 출력 되 었 다.나 무 를 특별한 그림 으로 본다 면 DFS 는 먼저 옮 겨 다 니 는 것 이다.따라서 역 추적 과 DFS 는 매우 밀접 한 관 계 를 가지 기 때문에 역 추적 은 DFS 의 응용 장면 이 라 고 볼 수 있다.또 DFS 는 깊이 만 저장 하고 광 도 는 저장 하지 않 는 다 는 장점 이 있다.그래서 공간 복잡 도가 비교적 적 고 시간 복잡 도가 비교적 크다.
마지막 으로 어떤 해 공간 은 매우 커서 매우 방대 한 나무 라 고 볼 수 있다. 이때 완전히 옮 겨 다 니 는 시간의 복잡 도 는 참 기 어렵다.이 때 는 여러 가 지 를 옮 겨 다 니 는 동시에 조건 을 검사 할 수 있 습 니 다. 특정한 가 지 를 옮 겨 다 닐 때 조건 이 만족 하지 않 으 면 뿌리 노드 로 돌아 가 다음 가 지 를 옮 겨 다 닐 수 있 습 니 다.이것 이 바로 '역 추적' 이라는 단어의 근원 이다.조건 에 따라 선택 적 으로 옮 겨 다 니 는 것 을 가지치기 나 가 지 를 나 누 어 경 계 를 정 하 는 것 이 라 고 한다.
LeetCode 784 알파벳 대소 문 자 는 문자열 S 를 모두 배열 하여 지정 합 니 다. 문자열 S 의 모든 알파벳 을 대소 문자 로 바 꾸 면 새로운 문자열 을 얻 을 수 있 습 니 다.얻 을 수 있 는 모든 문자열 집합 을 되 돌려 줍 니 다.사고방식: 역 추적 법 으로 위치 0 부터 문자 가 아니라면 문자열 temp 에 직접 추가 한 후 임시로 저장 하고 아래로 깊이 있 게 검색 합 니 다. 문자 라면 각각 대소 문자 로 역 추적 합 니 다. temp 가 S 의 길이 에 이 르 렀 을 때 결 과 를 저장 하고 위로 돌아 가 계속 역 추적 합 니 다.

 public List letterCasePermutation(String S) {
        Listlist=new ArrayList();
        String temp="";
        dfs(S,0,temp,list);
        return list;
    }
    public void dfs(String s,int i,String temp,List list){
        if(i==s.length())
            list.add(temp);
            return ;
        char c=s.charAt(i);
        if(!Character.isLetter(c)){
            dfs(s,i+1,temp+c,list);//   ，        
        }else{//    ，          
            dfs(s,i+1,temp+Character.toUpperCase(c),list);
            dfs(s,i+1,temp+Character.toLowerCase(c),list);
        }
    }

LeetCode 78 부분 집합 은 중복 요 소 를 포함 하지 않 은 정수 배열 nums 를 지정 하여 이 배열 의 가능 한 모든 부분 집합 (멱 집합) 을 되 돌려 줍 니 다.
설명: 해 집 은 중복 되 는 부분 집합 을 포함 할 수 없습니다.사고: 이 문제 에서 풀 수 있 는 나무 공간 은 이 진 트 리 로 모든 배열 의 요소 에 대해 두 가지 상황 으로 나 눌 수 있 습 니 다. 가입 과 가입 하지 않 습 니 다.

 public List> subsets(int[] nums) {
    List> list = new ArrayList<>();
    Listli=new ArrayList<>();
    backtrack(list, li, nums, 0);
    return list;
}

private void backtrack(List> list , List tempList, int [] nums, int start){
    
    list.add(new ArrayList<>(tempList));
    for(int i=start;i

leetcode 46 전체 배열 은 중복 되 지 않 은 숫자의 배열 을 정 하고 가능 한 모든 배열 을 되 돌려 줍 니 다.사고: 공간 나 무 는 배열 나무 로 뿌리 노드 에서 끝까지 거 슬러 올 라 가면 결 과 를 보존 하고 위로 거 슬러 올 라 가 반복 되 지 않도록 똑 같은 요 소 를 걸 러 내야 한다.

public List> permute(int[] nums) {
        List> list=new ArrayList<>();
        Listl=new ArrayList<>();
        backtrack(nums,list,l);
        return list;
    }
    private void backtrack(int []nums,List> list,Listl){
        if(l.size()==nums.length){
            list.add(new ArrayList<>(l));
        }else{
            for(int i=0;i

leetcode 39 조합 총 수 는 중복 요소 가 없 는 배열 candidates 와 하나의 목표 수 target 을 지정 하여 candidates 의 모든 숫자 와 target 의 조합 을 찾 습 니 다.
candidates 의 숫자 는 무제 한 중복 으로 선택 할 수 있 습 니 다.사고: 앞에서 부분 집합 문 제 를 푸 는 것 과 같은 사고 와 달리 매번 재 귀 는 그 자체 부터 시작 할 수 있 습 니 다. 요소 가 중복 되 기 때 문 입 니 다.

public List> combinationSum(int[] candidates, int target) {
        List> list=new ArrayList<>();
        Listl=new ArrayList<>();
        Arrays.sort(candidates);
        back(list,l,candidates,target,0);
        return list;
    }
    private void back( List> list, ListtempList,int []nums,int remain,int start){
      if(remain < 0) return;
      else if(remain == 0) list.add(new ArrayList<>(tempList));
      else{ 
        for(int i = start; i < nums.length; i++){
            tempList.add(nums[i]);
            back(list, tempList, nums, remain - nums[i], i); // not i + 1 because we can reuse same elements
            tempList.remove(tempList.size() - 1);
        }
    }
    }