LeetCode-47

题目

结果

代码

class Solution {
    // Save the final answer
    private final List<List<Integer>> ans = new ArrayList<>();
    // Check out If the num has been used before
    private boolean[] flag;

    public List<List<Integer>> permuteUnique(int[] nums) {
        // Special case
        if (nums.length == 0) {
            return ans;
        }
        // Initialize the flag array
        flag = new boolean[nums.length];
        dfs(nums, new ArrayList<>());
        // Remove the duplicate and return the final answer
        return ans.stream().distinct().collect(Collectors.toList());
    }

    private void dfs(int[] nums, List<Integer> tmp) {
        // Time to stop recursive call
        if (tmp.size() == nums.length) {
            ans.add(tmp);
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (!flag[i]) {
                flag[i] = true;
                List<Integer> newTmp = new ArrayList<>(tmp);
                newTmp.add(nums[i]);
                // Recursive call
                dfs(nums, newTmp);
                flag[i] = false;
            }
        }
    }
}