No.1

题目

思路

回溯法
不改变原有序列的情况下，查找递增子序列
注意在树上每一层用过的数字都不要再用了，不然会出现重复的

代码

private List<Integer> path;  
private List<List<Integer>> result;  
  
public void findHelper(int[] nums, int startIndex) {  
    if (path.size() > 1)  
        result.add(new ArrayList<>(path));  
    if (startIndex >= nums.length)  
        return;  
  
    Set<Integer> used = new HashSet<>();  
    for (int i = startIndex; i < nums.length; i++) {  
        if (!used.contains(nums[i]))  
            used.add(nums[i]);  
        else  
            continue;  
          
        if (path.size() == 0 || path.size() > 0 && nums[i] >= path.get(path.size() - 1)) {  
            path.add(nums[i]);  
            findHelper(nums, i + 1);  
            path.remove(path.size() - 1);  
        }  
    }  
}  
  
public List<List<Integer>> findSubsequences(int[] nums) {  
    path = new ArrayList<>();  
    result = new ArrayList<>();  
    findHelper(nums, 0);  
  
    return result;  
}

No.2

题目

全排列

思路

回溯法
排列和组合有些不同
- 排列中不用startIndex，而用used数组标记访问过的位置

代码

private List<Integer> path;  
private List<List<Integer>> result;  
  
public void permuteHelper(int[] nums, boolean[] used) {  
    if (path.size() == nums.length) {  
        result.add(new ArrayList<>(path));  
        return;  
    }  
  
    for (int i = 0; i < nums.length; i++) {  
        if (used[i])  
            continue;  
  
        used[i] = true;  
        path.add(nums[i]);  
        permuteHelper(nums, used);  
        path.remove(path.size() - 1);  
        used[i] = false;  
    }  
}  
  
public List<List<Integer>> permute(int[] nums) {  
    path = new ArrayList<>();  
    result = new ArrayList<>();  
    boolean[] used = new boolean[nums.length];  
    permuteHelper(nums, used);  
  
    return result;  
}

No.3

题目

全排列 II

思路

回溯法
输入数组中存在重复的元素，因此要在树的一层上去重
- 在树的一层上去重，可以用HashSet存放访问过的数字用于判断
- 也可以先给nums排序，然后用下面第二条判断（有点难想到）
  - used[i - 1] == true，说明同一树枝nums[i - 1]使用过
  - used[i - 1] == false，说明同一树层nums[i - 1]使用过
- 以上2个条件都可以用，分别是在树枝上去重和在树层上去重，树层上去重的效率更高（可以画树形图分析一下，树枝去重会做很多无用搜索）
- 本人一开始没加这个条件，相当于在树枝和树层上都去重，结果就错误了，最后选择了HashSet去重的方式

代码

private List<Integer> path;  
private List<List<Integer>> result;  
  
public void permuteHelper(int[] nums, boolean[] used) {  
    if (path.size() == nums.length) {  
        result.add(new ArrayList<>(path));  
        return;  
    }  
  
    Set<Integer> accessed = new HashSet<>();  
    for (int i = 0; i < nums.length; i++) {  
        if (used[i] || accessed.contains(nums[i]))  
            continue;  
  
        used[i] = true;  
        accessed.add(nums[i]);  
        path.add(nums[i]);  
        permuteHelper(nums, used);  
        path.remove(path.size() - 1);  
        used[i] = false;  
    }  
}  
  
public List<List<Integer>> permuteUnique(int[] nums) {  
    path = new ArrayList<>();  
    result = new ArrayList<>();  
    boolean[] used = new boolean[nums.length];  
    permuteHelper(nums, used);  
  
    return result;  
}

错误分析

使用以下代码去重的执行结果

for (int i = 0; i < nums.length; i++) {
	// 去重代码
	if (i > 0 && nums[i] == nums[i - 1]) {
		continue;
	}

	// 正常流程
	if (used[i] == false) {
		used[i] = true;//标记同⼀树⽀nums[i]使⽤过，防止同一树枝重复使用
		path.add(nums[i]);
		backTrack(nums, used);
		path.remove(path.size() - 1);//回溯，说明同⼀树层nums[i]使⽤过，防止下一树层重复
		used[i] = false;//回溯
	}
}