代码随想录day28【回溯】子集2 递增子序列 全排列 全排列2

子集2

leecode题目
思路：
其实是组合2 与子集问题的组合问题，与子集的区别是需要去重。

image.png

1. 先排序
2. 同一树层上重复取数， 就要过滤掉（for循环处理树层）

var subsetsWithDup = function(nums) {
    nums.sort();
  let path = [];
  let res = [];
  var backTracking = function (startIndex) {
      res.push([...path]);
    if (startIndex >= nums.length) {
      return;
    }
    for (let i = startIndex; i < nums.length; i++) {
        if(i > startIndex && nums[i] === nums[i - 1]) {
            continue
        }
      path.push(nums[i]);
        backTracking(i+1)
      path.pop()
    }
  };
  backTracking(0)
  return res
};

递增子序列

思路：
与子集2的区别；不能进行排序，否咋所有子序列均为递增子序列了。

image.png

var findSubsequences = function(nums) {
 let path=[]
  let res=[]
  
  var backTracking=function(startIndex){
    if(path.length>=2){
      res.push([...path])
    }
    let map=new Map()

    if(startIndex>=nums.length){
      return
    } 

    for(let i=startIndex;i<nums.length;i++){
      // 元素比path最后的数小，或者 与本层之前元素重复
      if((path.length>0 && nums[i] < path[path.length - 1]) || (map.has(nums[i]))){
        continue
      }
      map.set(nums[i])
      path.push(nums[i])
      backTracking(i+1)
      path.pop()
    }
  }

  backTracking(0)
  return res
};

全排列

分析：与组合问题的不同：排列是有序的，也就是说 [1,2] 和 [2,1] 是两个集合。因此不需要startIndex
排列问题需要一个used数组，标记已经选择的元素。
思路：

image.png

var permute = function(nums) {
   let path=[]
   let res=[]
   let used=[]
   var backTracking=function(){
       if(path.length === nums.length){
           res.push([...path])
           return
       }

       for(let i=0;i<nums.length;i++){
           if(used[i]){//记录元素是否使用过
               continue
           }
           path.push(nums[i])
           used[i]=true
           backTracking()
           path.pop()
           used[i]=false
       }
   }
   backTracking()
   return res
};

全排列2

与前一个问题 全排列的区别是：包含的数字可重复。
思路：

image.png

注意：
used[i-1]===false：树层去重

var permuteUnique = function(nums) {
    nums.sort((a, b) => {
        return a - b
    })
    let path=[]
    let res=[]
    let used=[]
    var backTracking=function(){
        if(path.length===nums.length){
            res.push([...path])
            return 
        }

        for(let i=0;i<nums.length;i++){
            if(i>=1 && nums[i]===nums[i-1] && used[i-1]===false){//  used[i-1]===false：树层去重
                continue
            }
            if(used[i]){//避免重复取元素
                continue
            }
            path.push(nums[i])
            used[i]=true
            backTracking()
            path.pop()
            used[i]=false
        }
    }
    backTracking()
    return res
};