[leetcode] Medium-47번. Permutations2 문제풀이

문제

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

Permutations II - LeetCode

 

 

 

 

풀이코드

package SITE03_leetcode.medium;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * https://leetcode.com/problems/permutations/
 */
public class M019_leetcode47_Permutations {
    List<List<Integer>> resultList = new ArrayList<List<Integer>>();
    List<Integer> paramList = new ArrayList<>();
    int[] map;
    int n;
    boolean[] visited;

    public static void main(String[] args) {
        M019_leetcode47_Permutations solution = new M019_leetcode47_Permutations();

        int[] dx = {1,1,2};
        //int[] dx = {0,1};

        System.out.println(solution.permuteUnique(dx));
    }

    public List<List<Integer>> permuteUnique(int[] nums) {
        this.map = nums;
        n = nums.length;

        visited = new boolean[n];

        dfs(paramList);

        return resultList;
    }

    public void dfs(List<Integer> paramList) {
        // 탈출 조건
        if (paramList.size() == n) {
            if(!resultList.contains(paramList)) {
                resultList.add(new ArrayList<>(paramList));
                return;
            }
        }

        // 구현
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                visited[i] = true;
                paramList.add(map[i]);


                dfs(paramList);

                visited[i] = false;
                paramList.remove(paramList.size() - 1);
            }
        }
    }
}

 

46번과의 차이점

https://devfunny.tistory.com/605?category=897198 

[leetcode] Medium-46번. Permutations 문제풀이

 

47번에서는 46번과 다르게 결과 리스트가 unique 해야한다. 따라서 46번의 정답에서 아래 if문-contains() 코드를 추가하여 해결하였다.

 

// 탈출 조건
if (paramList.size() == n) {
    if(!resultList.contains(paramList)) {
        resultList.add(new ArrayList<>(paramList));
        return;
    }
}