leetcode刷题day25|回溯算法Part04（491.递增子序列、46.全排列、47.全排列 II）

491.递增子序列

思路：至少有两个元素，说明递归的树枝至少有两层；要求递增，每次取数的时候要考虑下一个元素是不是大于当前元素。此外，这个题也要在同一层中进行去重，但是这个题不能对原数组进行排序，所以需要在每一层开辟一个新的空间HashSet来记录已经遍历过的元素。

HashSet 不允许重复元素。如果尝试添加一个已经存在的元素，该操作将被忽略。

回溯三部曲：
1、递归函数参数：全局变量：数组result存放结果集，path存放遍历到的每个节点。 递归函数参数：原数组；startIndex。
2、终止条件：startIndex遍历完数组，大于等于数组的长度；可以不需要加终止条件，因为startIndex >= nums.length，本层for循环本来也结束了。
3、单层搜索的逻辑：在for (int i = startIndex; i < s.size(); i++)循环中，我们定义了起始位置startIndex，那么 [startIndex, i] 就是要截取的子串。首先判断这个数组元素是不是小于前一个或者已经遍历过了，如果是，就continue。

代码如下：

class Solution {
    List<List<Integer>> result=new ArrayList<>();
    List<Integer> path=new LinkedList<>();
    public List<List<Integer>> findSubsequences(int[] nums) {
        backTracking(nums,0);
        return result;
    }
    public void backTracking(int[] nums,int startIndex){
        if(path.size()>1) result.add(new ArrayList(path));
        HashSet<Integer> hs=new HashSet<>();  
        for(int i=startIndex;i<nums.length;i++){
            if((!path.isEmpty() && path.get(path.size()-1)>nums[i]) || hs.contains(nums[i])) continue;
            hs.add(nums[i]);
            path.add(nums[i]);
            backTracking(nums,i+1);
            path.remove(path.size()-1);
        }
    }
}

46.全排列

思路：全排列相对于组合问题不需要设置startIndex，但是需要判断这个元素是不是已经在该树枝中用过了，如果用过则跳过循环。

class Solution {
    List<List<Integer>> result=new ArrayList<>();
    List<Integer> path= new LinkedList<>();
    public List<List<Integer>> permute(int[] nums) {
        backTracking(nums);
        return result;
    }
    public void backTracking(int[] nums){
        if(path.size()==nums.length){
            result.add(new ArrayList(path));
            return;
        }
        for(int i=0;i<nums.length;i++){
            if(path.contains(nums[i])) continue;
            path.add(nums[i]);
            backTracking(nums);
            path.removeLast();
        }
    }
}

47.全排列 II

思路：由于该题目中序列 nums 可包含重复数字，所以需要在同一层去重。

class Solution {
    List<List<Integer>> result=new ArrayList<>();
    List<Integer> path=new LinkedList<>();
    boolean[] used;
    public List<List<Integer>> permuteUnique(int[] nums) {
        used=new boolean[nums.length];
        Arrays.fill(used, false);
        Arrays.sort(nums);
        backTracking(nums,used);
        return result;
    }
    public void backTracking(int[] nums,boolean[] used){
        if(path.size()==nums.length){
            result.add(new ArrayList(path));
            return;
        }
        for(int i=0;i<nums.length;i++){
            if(i>0 && nums[i]==nums[i-1] && used[i-1]==false) continue;
            if (used[i] == false) {
                path.add(nums[i]);
                used[i]=true;
                backTracking(nums,used);
                used[i]=false;
                path.removeLast();
            }
        }
    }
}

注意：
下面是对树层去重，两个元素相同，但之前没遍历过（used层与层之间是独立的）：

if(i>0 && nums[i]==nums[i-1] && used[i-1]==false) continue;

下面是对数枝去重，两个元素相同，但前一个遍历过了：

if(i>0 && nums[i]==nums[i-1] && used[i-1]==true) continue;

原文地址：https://blog.csdn.net/m0_51007517/article/details/142421534

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！