[LeetCode- Ch9. 백트래킹] 2. 순열 #

https://leetcode.com/problems/permutations/

Permutations - LeetCode

 

1. 배열에 [1,2,3]이 존재한다면 -> 1부터 시작해 배열의 길이만큼 깊이 우선 탐색 

2. 배열의 길이만큼 깊이 우선 탐색시 -> 마지막 값 삭제 후, 다시 깊이 우선 탐색 수행

3. 현재 배열의 길이와 주어진 배열의 길이가 같을 때, 해당 리스트를 결과에 담는다.

 

class Solution {
    //순열 : 순서에 존재하는 나열
    //조합 : 순서가 존재하지 않는 뽑기
    
    //주어진 배열의 순열을 리턴
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        
        //예외처리
        if(nums==null || nums.length==0) return result;
        
        DFS(nums, result, list);
        return result;
    }
    
    private void DFS(int[] nums, List<List<Integer>> result, List<Integer> cur){
        //1. current에 해당하는 리스트 저장
        if(cur.size()==nums.length){
            List<Integer> list = new ArrayList<>(cur);
            result.add(list);
        }
        
        //2. for 저장, 탈출
        //(1) 깊이 우선 탐색 수행 : DFS 
        //(2) 탈출 조건 설정     : 모두 담을 경우 (알맞게 도는 지 확인), 한번 들어온 값은 제외한 경우
        //(3) 제약 조건 설정     : 마지막 값 삭제
        for(int i=0;i<nums.length;i++){
            //탈출 조건
            //(1)  모두 담을 경우
            //if(cur.size()==nums.length) continue;
            //(2) 한번 들어온 값 제외하고 담는다.
            if(cur.contains(nums[i])) continue;
            
            cur.add(nums[i]);
            DFS(nums, result, cur);
            cur.remove(cur.size()-1);
        }       
    }
}