1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114

/*
 * @lc app=leetcode id=47 lang=java
 *
 * [47] Permutations II
 *
 * https://leetcode.com/problems/permutations-ii/description/
 *
 * algorithms
 * Medium (58.51%)
 * Likes:    8373
 * Dislikes: 139
 * Total Accepted:    893.1K
 * Total Submissions: 1.5M
 * Testcase Example:  '[1,1,2]'
 
 * Given a collection of numbers, nums, that might contain duplicates, return
 * all possible unique permutations in any order.
 * 
 * 
 * Example 1:
 * 
 * 
 * Input: nums = [1,1,2]
 * Output:
 * [[1,1,2],
 * ⁠[1,2,1],
 * ⁠[2,1,1]]
 * 
 * 
 * Example 2:
 * 
 * 
 * Input: nums = [1,2,3]
 * Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
 * 
 * 
 * 
 * Constraints:
 * 
 * 
 * 1 <= nums.length <= 8
 * -10 <= nums[i] <= 10
 * 
 * 
 */

// @lc code=start

import java.util.Arrays;

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<Integer> path = new ArrayList<>();
        int len = nums.length;
        Arrays.sort(nums);
        boolean [] used = new boolean[len];
        backTrack(nums, path, used);
        return result;
    }

    public void backTrack(int[] nums, List<Integer> path,boolean [] used ){
        if(nums.length == path.size()){
            result.add(new ArrayList<>(path));
            return;
        }

        for(int i = 0 ; i < nums.length; i++){
            //然后只有在以下情况下选择元素：它沒被選擇過。它是第一个要选择的元素，它与前一个元素不同，或者它与前一个元素相同，但前一个元素也已经被选择。
            if(!used[i] && (i==0 || nums[i] != nums[i-1] || used[i-1])){
                path.add(nums[i]);
                used[i] = true;
                backTrack(nums, path, used);
                used[i] = false;
                path.removeLast();
            }
        }
    }
}


// class Solution2 {
//     List<List<Integer>> result = new ArrayList<>();
//     public List<List<Integer>> permuteUnique(int[] nums) {
//         List<Integer> path = new ArrayList<>();
//         int len = nums.length;
//         boolean [] used = new boolean[len];
//         backTrack(nums, path, used);
//         List<List<Integer>> deduped = result.stream()
//                 .distinct()
//                 .toList();
//         return deduped;
//     }

//     public void backTrack(int[] nums,
//      List<Integer> path,boolean [] used ){
//         if(nums.length == path.size()){
//             result.add(new ArrayList<>(path));
//             return;
//         }

//         for(int i = 0 ; i < nums.length; i++){
//             if(!used[i]){
//                 path.add(nums[i]);
//                 used[i] = true;
//                 backTrack(nums, path, used);
//                 used[i] = false;
//                 path.removeLast();
//             }
//         }
//     }
// }

// @lc code=end