2022-07-25

LeetCode回溯法经典题目

SubSet

Given a set of distinct integers, S, return all possible subsets.

Note:

Elements in a subset must be in non-descending order.
The solution set must not contain duplicate subsets.

For example,
If S =[1,2,3], a solution is:

[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> list = new ArrayList<>();
    Arrays.sort(nums);
    backtrack(list, new ArrayList<>(), nums, 0);
    return list;
}

private void backtrack(List<List<Integer>> list , List<Integer> tempList, int [] nums, int start){
    list.add(new ArrayList<>(tempList));
    for(int i = start; i < nums.length; i++){
        tempList.add(nums[i]);
        backtrack(list, tempList, nums, i + 1);
        tempList.remove(tempList.size() - 1);
    }
}

SubSet-ii

Given a collection of integers that might contain duplicates, S, return all possible subsets.

Note:

Elements in a subset must be in non-descending order.
The solution set must not contain duplicate subsets.

For example,
If S =[1,2,2], a solution is:

[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]

public List<List<Integer>> subsetsWithDup(int[] nums) {
    List<List<Integer>> list = new ArrayList<>();
    Arrays.sort(nums);
    backtrack(list, new ArrayList<>(), nums, 0);
    return list;
}

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, int start){
    list.add(new ArrayList<>(tempList));
    for(int i = start; i < nums.length; i++){
        if(i > start && nums[i] == nums[i-1]) continue; // skip duplicates
        tempList.add(nums[i]);
        backtrack(list, tempList, nums, i + 1);
        tempList.remove(tempList.size() - 1);
    }
}

Permutations

Given a collection of numbers, return all possible permutations.

For example,
[1,2,3]have the following permutations:

[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2], and[3,2,1].

public List<List<Integer>> permute(int[] nums) {
   List<List<Integer>> list = new ArrayList<>();
   // Arrays.sort(nums); // not necessary
   backtrack(list, new ArrayList<>(), nums);
   return list;
}

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums){
   if(tempList.size() == nums.length){
      list.add(new ArrayList<>(tempList));
   } else{
      for(int i = 0; i < nums.length; i++){
         if(tempList.contains(nums[i])) continue; // element already exists, skip
         tempList.add(nums[i]);
         backtrack(list, tempList, nums);
         tempList.remove(tempList.size() - 1);
      }
   }
}

Permutations-ii

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example,
[1,1,2]have the following unique permutations:

[1,1,2],[1,2,1], and[2,1,1].

public List<List<Integer>> permuteUnique(int[] nums) {
    List<List<Integer>> list = new ArrayList<>();
    Arrays.sort(nums);
    backtrack(list, new ArrayList<>(), nums, new boolean[nums.length]);
    return list;
}

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, boolean [] used){
    if(tempList.size() == nums.length){
        list.add(new ArrayList<>(tempList));
    } else{
        for(int i = 0; i < nums.length; i++){
            if(used[i] || i > 0 && nums[i] == nums[i-1] && !used[i - 1]) continue;
            //!used[i - 1]保证了i-1和i这个字母在同一层遍历中，used[i - 1]=true表明当前i是下一层
            used[i] = true;
            tempList.add(nums[i]);
            backtrack(list, tempList, nums, used);
            used[i] = false;
            tempList.remove(tempList.size() - 1);
        }
    }
}

对于排列的问题，我们每次都要遍历整个 num，如果他有重复的字母，正因为需要遍历所有的 num，因此我们需要记录每一个字母的状态，保证在一个 epoch 里面，这一个和上一个字母一样的情况下，我们只使用一次当前的字母。

而其他的情况，不规定每一次要用所有的字母，从们按照顺序执行，已经在顺序中去除了重新遍历可能会得到之前用过的字母的情况，因此只需要 skip 掉重复的字母即可。

树的遍历

path-sum-li

Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.

For example:
Given the below binary tree andsum = 22,

      5
     / \
    4   8
   /   / \
  11  13  4
 /  \    / \
7    2  5   1

return

[
   [5,4,11,2],
   [5,8,4,5]
]

import java.util.*;
public class Solution {
    ArrayList<ArrayList<Integer>> result=new ArrayList<ArrayList<Integer>>();
    public ArrayList<ArrayList<Integer>> pathSum(TreeNode root, int sum) {
        if(root==null) return result;

        dfs(root,sum,new ArrayList<>());
        return result;
    }
    public void dfs(TreeNode node,int target,ArrayList<Integer> list){
        if(node==null) return;
        list.add(node.val);
        if(node.left==null&&node.right==null&&target==node.val){
            result.add(new ArrayList<>(list));
            list.remove(list.size()-1);//注意此时必须进行回溯，因为left和right共同指向了list，当左节点符合时，有可能右节点也符合，因此必须撤销这一点
            return;
        }
        dfs(node.left,target-node.val,list);
        dfs(node.right,target-node.val,list);
        list.remove(list.size()-1);//同理，这里回溯是因为node的父节点的左右节点指向了同一个list，我们必须保证右节点，即node的兄弟的list不跟在node节点之后。
    }
}

对于树的回溯与遍历，从根节点到叶子节点，我们必须注意 path 中，在最后的叶子节点，对于新加入的点的回溯，因为 left 和 right 共同指向了 list，当左节点符合时，有可能右节点也符合，因此必须撤销这一点。

binary-tree-maximum-path-sum

任意 node 到任意 node

Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

For example:
Given the below binary tree,

1
2
3

  1
 / \
2   3

Return 6

public class Solution {
    int max=0;
    public int maxPathSum(TreeNode root) {
        if(root==null)  return 0;
        //当只有一个节点的时候，直接返回root的值
        if(root.left==null&&root.right==null) return root.val;

        max=Integer.MIN_VALUE;
        getMax(root);
        return max;
    }
    public int getMax(TreeNode node){
        if(node==null) return 0;
        int left=Math.max(0,getMax(node.left));
        int right=Math.max(0,getMax(node.right));
        max=Math.max(max,node.val+left+right);
        //返回当前节点下的最大路径，用于给上一层的left或者right
        //临时变量通过return传递，最大值通过全局max变量保存
        return Math.max(left,right)+node.val;
    }
}