[LeetCode] 46. Permutations - 깊이우선탐색(DFS) + 비트마스킹(BitMask) JAVA

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

코드설명

깊이우선탐색(DFS) + 비트마스킹(BitMask)을 활용합니다.

 

일반적인 순열 탐색 방식입니다. 

코드

정답코드1입니다.

class Solution {
    public List<List<Integer>> permute(int[] nums) {        
        return DFS(0, new int[nums.length], nums, (1 << (nums.length + 1) ), new ArrayList<>() );
    }

    List<List<Integer>> DFS(int level, int[] A, int[] nums, int visited, List<List<Integer>> answer){
        if(level == nums.length){
            List<Integer> arr = new ArrayList<>();
            for(int i=0; i<A.length; i++) arr.add(A[i]);
            answer.add(arr);
            return answer;
        }

        for(int i=0; i<nums.length; i++){
            if( (visited & (1 << i) ) == 0 ){
                visited |= (1 << i);  
                A[level] = nums[i];
                answer = DFS(level + 1, A, nums, visited, answer);
                visited &= ~(1 << i);
            }
        }
        return answer;
    }

}

 

정답코드2입니다.

class Solution {
    public List<List<Integer>> permute(int[] nums) {        
        return DFS(0, new int[nums.length], nums, (1 << (nums.length + 1) ), new ArrayList<>() );
    }

    List<List<Integer>> DFS(int level, int[] A, int[] nums, int visited, List<List<Integer>> answer){
        if(level == nums.length){
            List<Integer> arr = new ArrayList<>();
            for(int i=0; i<A.length; i++) arr.add(A[i]);
            answer.add(arr);
            return answer;
        }

        for(int i=0; i<nums.length; i++){
            if( (visited & (1 << i) ) == 0 ){
                visited += (1 << i);
                A[level] = nums[i];
                answer = DFS(level + 1, A, nums, visited, answer);
                visited &= ~(1 << i);
            }
        }
        return answer;
    }

}