47. 全排列 II

原题链接：

47. 全排列 II

https://leetcode.cn/problems/permutations-ii/submissions/

完成情况：

解题思路：

推荐还是得用boolean 数组去判别一下是否访问过了。

参考代码：

package 代码随想录.回溯;

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

public class _47全排列II_允许重复字符_构建数组回溯 {
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    List<Integer> listSubset = new ArrayList<Integer>();
    private boolean used[];

    /**
     * 在46的基础上，允许出现重复字符
     *
     * @param nums
     * @return
     */
    public List<List<Integer>> permuteUnique(int[] nums) {
        if (nums.length == 0) {
            return result;
        }
        used = new boolean[nums.length];
        //Arrays.fill(used,false);
        Arrays.sort(nums);
        backTrack(nums);    //没有先后顺序，返回所有排列结果
        return result;
    }

    /**
     * @param nums
     */
    private void backTrack(int[] nums) {
        if (listSubset.size() == nums.length) {
            result.add(new ArrayList<>(listSubset));
            return;
        }
        // used[i - 1] == true，说明同?树?nums[i - 1]使?过
        // used[i - 1] == false，说明同?树层nums[i - 1]使?过
        // 如果同?树层nums[i - 1]使?过则直接跳过
        for (int i = 0; i < nums.length; i++) {
            if (i>0 && nums[i] == nums[i-1] && used[i-1] == false){
                continue;
            }
            //如果同?树?nums[i]没使?过开始处理
            if (used[i]){
                continue;
            }
            used[i] = true;
            listSubset.add(nums[i]);
            backTrack(nums);
            listSubset.remove(listSubset.size() - 1);
            used[i] = false;
        }
    }
}

错误经验吸取