[LeetCode] Permutations

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

 

 

 

문제 파악

주어진 배열로 만들 수 있는 모든 순열 구하기

• 1 <= nums.length <= 6
• 10 <= nums[i] <= 10
• All the integers of nums are unique. (요소 중복 허용)

접근 방법

💡 -재귀 함수가 리턴되면 마지막에 호출한 함수가 가장 먼저 리턴

-리턴 되면 리스트에서 해당 원소 삭제, 방문 배열 초기화 -<순열> : 중복 허용, 순서 존재

-방문 배열은 하나의 순열 안에서 이루어지는 것을 유의하자.

해당 원소에 해당하는 경우의 수를 모두 순회하면서 겹치지 않게 표시

 

코드 구현

import java.util.*;
class Solution {
    //순열 문제 : 중복 허용, 순서 존재
    public List<List<Integer>> permute(int[] nums) {
        boolean[] visited = new boolean[nums.length];
        List<List<Integer>> result = new ArrayList<>();

        backtrack(visited,nums,result,new ArrayList<>());
        return result;
    }
    public void backtrack(boolean[] visited,int[] nums,List<List<Integer>> result,List<Integer> curr){
        if(nums.length == curr.size()){
            result.add(new ArrayList<>(curr));
            return;
        }
        for(int i=0;i<nums.length;i++){
            if(visited[i]) continue;
            curr.add(nums[i]);
            visited[i] = true;
            backtrack(visited,nums,result,curr);
            curr.remove(curr.size()-1);
            visited[i] = false;
            //함수 종료 후 [1,2,3,4] 였다면 3을 선택한 때로 돌아간다.- backtracking 다음구문 remove
        }

    }
}

배우게 된 점

1. visited 배열은 [1,1, ] 방지!! 같은 순열 안에서 중복을 방지하기 위함
2. [메모리 측면] curr를 직접 넣으면 curr를 가리키게 되어서 curr변경 시 result에도 반영되므로 new 로 새로운 공간에 복사해야 한다!

result.add(new ArrayList<>(curr));

1. curr 리스트의 마지막 요소를 제거

⇒ 순차적으로 쌓이고 순차적으로 제거(리턴)된다.

curr.remove(curr.size()-1);

1. -curr.contains(nums[i]) = O(n)

-visited[i] = O(1)