代码随想录刷题随记24-回溯

491. 非递减子序列

leetcode链接

与之前的集合问题不同，而本题求自增子序列，是不能对原数组进行排序的，排完序的数组都是自增子序列了。所以不能通过排序的问题去重

class Solution {
    List<List<Integer>> ret=new ArrayList<>();
    List<Integer> path=new LinkedList<>();

    void backtrace(int startindex,int []nums){
        if(path.size()>=2){
            ret.add(new ArrayList<>(path));
        }
        HashSet<Integer> used=new HashSet<>();
    
        for(int i=startindex;i<nums.length;i++){
            if(!path.isEmpty()&&nums[i]<path.getLast()||used.contains(nums[i])){
                continue;
            }
            path.add(nums[i]);
            used.add(nums[i]);
            backtrace(i+1, nums);
            path.removeLast();
        }
    }
    public List<List<Integer>> findSubsequences(int[] nums) {
           backtrace(0, nums);
           return ret;
    }
}

46.全排列

leetcode链接

class Solution {
    public List<List<Integer>> ret=new ArrayList<>();
    List<Integer> path=new ArrayList<>();
    void backtrace(int []nums,boolean []used){
        if(path.size()==nums.length){
            ret.add(new ArrayList<>(path));
            return;
        }
        for(int i=0;i<nums.length;i++){
            if(used[i])
               continue;
            path.add(nums[i]);
            used[i]=true;
            backtrace(nums, used);
            path.removeLast();
            used[i]=false;
        }
    }
    public List<List<Integer>> permute(int[] nums) {
        boolean []used=new boolean[nums.length];
        for (boolean a:used){
            a=false;
        }
        backtrace(nums,used);
        return ret;
    }
}

47.全排列 II

leetcode链接
与上一题的区别在于：给定一个可包含重复数字的序列 nums

class Solution {
    List<List<Integer>>  ret=new ArrayList<>();
    List<Integer> path=new LinkedList<>();
     void backtrace(int [] num,boolean[] used){
        if(path.size()==num.length){
            ret.add(new ArrayList<>(path));
            return;
        }
        HashSet<Integer> setmy=new HashSet<>();
        for(int i=0;i<num.length;i++){
           if(setmy.contains(num[i])||(!path.isEmpty()&& used[i])){
             continue;
           }
           setmy.add(num[i]);
           path.add(num[i]);
           used[i]=true;
           backtrace(num, used);
           path.removeLast();
           used[i]=false;
        }
     }

    public List<List<Integer>> permuteUnique(int[] nums) {
        boolean[] used=new boolean[nums.length];
        for (boolean a:used){
            a=false;
        }
      backtrace(nums, used);
      return ret;
    }
}