Permutations

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

Permutations - LeetCode

 

 

주어진 배열의 순열을 모두 뽑아내는 문제이다. 가장 기본적인 형태의 알고리즘의 문제이다.
주어진 배열을 직접 스왑하면서 푸는 방식도 있지만 일반적인 백트래킹 방식으로도 해결할 수 있다.

백트래킹을 할 때는 항상 재귀 함수 이후 원 상태로 돌려주어야 한다는 점이다. 아래는 통과한 전체 코드이다.

import java.util.*;  
  
public class Solution {  
    public List<List<Integer>> permute(int[] nums) {  
        List<List<Integer>> answer = new ArrayList<>();  
        List<Integer> list = new ArrayList<>();  
        boolean[] visited = new boolean[nums.length];  
        dfs(nums, list, answer, visited);  
  
        return answer;  
    }  
  
    private void dfs(int[] nums, List<Integer> cur, List<List<Integer>> answer, boolean[] visited){  
        if(cur.size() == nums.length){  
            answer.add(new ArrayList<>(cur));  
            return;  
        }  
  
        for(int i = 0; i < nums.length; i++){  
            if(!visited[i]){  
                visited[i] = true;  
                cur.add(nums[i]);  
                int removeIdx = cur.size() - 1;  
                dfs(nums, cur, answer, visited);  
                cur.remove(removeIdx);  
                visited[i] = false;  
            }  
        }  
    }  
}