90. 子集 II

这一题就是典型的used横向剪枝与index纵向剪枝共同运用的题目
直接看代码：
即与顺序有关，与数也有关，用过的数不能再用了 

  1. /// 90. 子集II
  2. pub fn subsets_with_dup(mut nums: Vec<i32>) -> Vec<Vec<i32>> {
  3.     nums.sort();
  4.     let mut res: Vec<Vec<i32>> = Vec::new();
  5.     let mut temp = Vec::new();
  6.     let mut used = vec![false; nums.len()];
  7.     Self::dfs(0, &mut nums, &mut res, &mut temp, &mut used);
  8.     res
  9. }
  11. fn dfs(cur: usize, nums: &mut Vec<i32>, res: &mut Vec<Vec<i32>>,
  12.        temp: &mut Vec<i32>, used: &mut Vec<bool>)
  13. {
  14.     res.push(temp.clone());
  15.     if cur == nums.len() {
  16.         return;
  17.     }
  18.     for x in cur..nums.len() {
  19.         // 横向剪枝
  20.         if x > 0 && !used[x-1] && nums[x] == nums[x-1] {
  21.             continue;
  22.         }
  24.         used[x] = true;
  25.         temp.push(nums[x]);
  26.         // 递归方向剪枝
  27.         Self::dfs(x + 1, nums, res, temp, used);
  28.         temp.pop();
  29.         used[x] = false;
  30.     }
  32. }

子集——index方案

如果说上一题是完整的两种方法的运用，这一题就是只运用index技巧的题目
这一题的特点在于：不重复元素、用过的元素不能再用、在过程中间就得存储

  1. /// 78. 子集
  2. pub fn subsets(mut nums: Vec<i32>) -> Vec<Vec<i32>> {
  3.     fn dfs(index: usize, nums: &mut Vec<i32>, temp: &mut Vec<i32>, res: &mut Vec<Vec<i32>>) {
  4.         // 因为要获取到每一个子阶段的数据，因此在这里push
  5.         res.push(temp.clone());
  6.         if index == nums.len() {
  7.             return;
  8.         }
  9.         for x in index..nums.len() {
  10.             temp.push(nums[x]);
  11.             dfs(x + 1, nums, temp, res);
  12.             temp.pop();
  13.         }
  14.     }
  16.     nums.sort();
  17.     let mut res: Vec<Vec<i32>> = Vec::new();
  18.     let mut temp = Vec::new();
  19.     dfs(0, &mut nums, &mut temp, &mut res);
  20.     res
  21. }

全排列——used方案

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
这一题的树与子集问题的比起来明显的差别就在于：

  1. 数是可以重复选择的，不是说，我考虑了存在1的情况就完事了，我需要考虑1放在什么位置的情况，即与顺序有关，与数无关

  2. 数列的重复当且仅当所有数一样时

    1. /// 46. 全排列
    2. pub fn permute(mut nums: Vec<i32>) -> Vec<Vec<i32>> {
    3.  let mut res: Vec<Vec<i32>> = Vec::new();
    4.  fn dfs(nums: &mut Vec<i32>, temp: &mut Vec<i32>, res: &mut Vec<Vec<i32>>,
    5.         used: &mut Vec<bool>, depth: usize) {
    6.      if depth == nums.len() {
    7.          res.push(temp.clone());
    8.          return;
    9.      }
    10.      for x in 0..nums.len() {
    11.          if used[x] {
    12.              continue;
    13.          }
    14.          used[x] = true;
    15.          temp.push(nums[x]);
    16.          dfs(nums, temp, res, used, depth + 1);
    17.          used[x] = false;
    18.          temp.pop();
    19.      }
    20.  }
    21.  let mut temp = Vec::new();
    22.  let mut used = vec![false; nums.len()];
    23.  dfs(&mut nums, &mut temp, &mut res, &mut used, 0);
    25.  res
    26. }

    全排列II——进阶的used

    给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
    对于重复元素的处理方式，还是通过used，不同之处在于需要排序以及判断
    !used[x-1] && nums[x] == nums[x-1]
    这也是子集II中的思路来源：
    可以看看树：
    明显的可以看出来，因为第二颗子树中需要再次用到1所以无法纵向剪枝，使用index
    而我们需要剪枝重复使用过的数，具体来说是，重复在同一位置的数。
    即与顺序有关，与数无关，可以使用多个一样的数
    因此使用了used的进化版
    排列问题 - 图1

    1. /// 47. 全排列 II
    2. pub fn permute_unique(mut nums: Vec<i32>) -> Vec<Vec<i32>> {
    3.  nums.sort();
    4.  let mut res: Vec<Vec<i32>> = Vec::new();
    5.  fn dfs(nums: &mut Vec<i32>, temp: &mut Vec<i32>, res: &mut Vec<Vec<i32>>,
    6.         used: &mut Vec<bool>, depth: usize) {
    7.      if depth == nums.len() {
    8.          res.push(temp.clone());
    9.          return;
    10.      }
    11.      for x in 0..nums.len() {
    12.          if used[x] {
    13.              continue;
    14.          }
    15.          if x > 0 && !used[x-1] && nums[x] == nums[x-1] {
    16.              continue;
    17.          }
    18.          used[x] = true;
    19.          temp.push(nums[x]);
    20.          dfs(nums, temp, res, used, depth + 1);
    21.          used[x] = false;
    22.          temp.pop();
    23.      }
    24.  }
    25.  let mut temp = Vec::new();
    26.  let mut used = vec![false; nums.len()];
    27.  dfs(&mut nums, &mut temp, &mut res, &mut used, 0);
    29.  res
    30. }

    剑指 Offer 38. 字符串的排列——定长排列问题

    这一题很像全排列II，使用进阶的used，但是不适用index
    再次思考index究竟使用在什么地方，这一题的特征和组合问题比较起来就是在两种可能上：考虑[1,1,2]

  3. 组合问题就是[1,2,1]与[1,1,2]一样，因此在2的时候不能再用1，所以使用index

  4. 排列问题就是[1,2,1]与[1,1,2]不一样，因此使用used

    1. /// 剑指 Offer 38. 字符串的排列
    2. pub fn permutation(mut s: String) -> Vec<String> {
    3.  let n = s.len();
    4.  // 相比于使用四字节的chars的UTF8模式，u8能够节省一些空间，但是比较不方便
    5.  let mut s: Vec<char> = s.chars().collect();
    6.  s.sort();
    8.  fn dfs(res: &mut Vec<String>, used: &mut Vec<bool>, depth: usize,
    9.         temp: &mut String, s: &mut Vec<char>) {
    10.      if depth >= s.len() {
    11.          res.push(temp.clone());
    12.          return;
    13.      }
    15.      for x in 0..s.len() {
    16.          if used[x] {continue; }
    17.          if x > 0 && s[x-1] == s[x] && !used[x-1] {
    18.              continue;
    19.          }
    20.          used[x] = true;
    21.          temp.push(s[x]);
    22.          dfs(res, used, depth+1, temp, s);
    23.          temp.pop();
    24.          used[x] = false;
    25.      }
    26.  }
    28.  let mut ans = Vec::new();
    29.  let mut temp = String::new();
    30.  let mut used = vec![false; s.len()];
    31.  dfs(&mut ans, &mut used, 0, &mut temp, &mut s);
    33.  ans
    34. }