组合

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
很像子集的思路

  1. // 注意输入输出
  2. 输入：n = 4, k = 2
  3. 输出：
  4. [
  5.   [2,4],
  6.   [3,4],
  7.   [2,3],
  8.   [1,2],
  9.   [1,3],
  10.   [1,4],
  11. ]

因此，组合类题目的特点与排列的不太一样：

  1. 数不是位置不重复，而是数本身不能重复——即不存在顺序不同
  2. 结果相同只取决于所有的元素相同，不再考虑需要顺序一模一样

思路就是index

  1. /// 组合
  2. pub fn combine(n: i32, k: i32) -> Vec<Vec<i32>> {
  3.     fn dfs(index: i32, n: i32, k: i32, depth: i32,
  4.            temp: &mut Vec<i32>, res: &mut Vec<Vec<i32>>) {
  5.         // 与集合不同之处1：index不再能够体现深度
  6.         if depth == k {
  7.             // 与集合不同之处2：只在固定长度取
  8.             res.push(temp.clone());
  9.             return;
  10.         }
  11.         for x in index..=n {
  12.             temp.push(x);
  13.             dfs(x + 1, n, k, depth+1, temp, res);
  14.             temp.pop();
  15.         }
  16.     }
  17.     let mut temp = Vec::new();
  18.     let mut res = Vec::new();
  19.     dfs(1, n, k, 0, &mut temp, &mut res);
  20.     res
  21. }

39. 组合总和

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被 选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。

这一题其实就是组合的基础上加上了和这个条件
特点在于：

  1. 数可以重复选，是无限的
  2. 和顺序无关，和数的数量有关

这一类题的思路是：index不是+1了，而是每次下去的时候可以遍历到自身
数很有特点：
我们index放置的位置就一目了然了
组合问题 - 图1
代码：

  1. /// 39. 组合总和
  2. pub fn combination_sum(mut candidates: Vec<i32>, target: i32) -> Vec<Vec<i32>> {
  3.     fn dfs(can: &mut Vec<i32>, mut tar: i32, index: usize,
  4.            ans: &mut Vec<Vec<i32>>, temp: &mut Vec<i32>) {
  5.         if tar<=0 {
  6.             if tar == 0 { ans.push(temp.clone()); }
  7.             return;
  8.         }
  9.         for x in index..can.len() {
  10.             tar -= can[x];
  11.             temp.push(can[x]);
  12.             // 核心区别在这里，不再是x+1
  13.             dfs(can, tar, x, ans, temp);
  14.             temp.pop();
  15.             tar += can[x];
  16.         }
  17.     }
  18.     let mut ans = Vec::new();
  19.     let mut temp = Vec::new();
  20.     dfs(&mut candidates, target, 0, &mut ans, &mut temp);
  21.     ans
  22. }

40. 组合总和 II

这一题就变成了子集II了

/// 40. 组合总和 II
pub fn combination_sum2(mut candidates: Vec<i32>, target: i32) -> Vec<Vec<i32>> {
    candidates.sort();
    fn dfs(can: &mut Vec<i32>, mut tar: i32, index: usize,
           ans: &mut Vec<Vec<i32>>, temp: &mut Vec<i32>, used: &mut Vec<bool>) {
        if tar<=0 {
            if tar == 0 { ans.push(temp.clone()); }
            return;
        }
        for x in index..can.len() {
            // 这个剪枝一定要有，大剪枝
            if tar - can[x] < 0 {
                break;
            }
            if x > 0 && !used[x - 1] && can[x] == can[x-1] {
                continue;
            }
            used[x] = true;
            tar -= can[x];
            temp.push(can[x]);
            dfs(can, tar, x+1, ans, temp, used);
            temp.pop();
            tar += can[x];
            used[x] = false;
        }
    }
    let mut ans = Vec::new();
    let mut temp = Vec::new();
    let mut used = vec![false; candidates.len()];
    dfs(&mut candidates, target, 0, &mut ans, &mut temp, &mut used);
    ans
}

四数之和

这一题很像子集II，但是DFS时间会很长，凭借Rust的特性能够过去，但是最好的做法还是多指针

/// 18. 四数之和:高为4的组合问题
pub fn four_sum(mut nums: Vec<i32>, target: i32) -> Vec<Vec<i32>> {
    nums.sort();
    fn dfs(nums: &mut Vec<i32>, mut tar: i32, index: usize,
           temp: &mut Vec<i32>, res: &mut Vec<Vec<i32>>) {
        if temp.len() >= 4 {
            if tar == 0 {
                res.push(temp.clone());
            }
            return;
        }

        for x in index..nums.len() {
            // 第一个大剪枝
            if nums.len() - x < 4 - temp.len() {
                return;
            }

            if x > index && nums[x] == nums[x - 1] {
                continue;
            }
            temp.push(nums[x]);
            tar -= nums[x];
            dfs(nums, tar, x +1, temp, res);
            temp.pop();
            tar += nums[x];
        }
    }
    let mut res = Vec::new();
    let mut temp = Vec::new();
    dfs(&mut nums, target, 0, &mut temp, &mut res);
    res
}

组合总和III

数字不可重复，使用过的数字不能再用，即位置不同也相同
因此就是index：

/// 216. 组合总和 III
pub fn combination_sum3(k: i32, n: i32) -> Vec<Vec<i32>> {
    fn dfs(k: i32, mut tar: i32, index: usize,
           res: &mut Vec<Vec<i32>>, temp: &mut Vec<i32>) {
        if temp.len() >= k as usize {
            if tar == 0 { res.push(temp.clone()); }
            return;
        }

        for x in index..=9 {
            if tar - (x as i32) < 0 {
                break;
            }
            temp.push(x as i32);
            tar -= x as i32;
            dfs(k, tar, x + 1, res, temp);
            tar += x as i32;
            temp.pop();
        }
    }
    let mut res = Vec::new();
    let mut temp = Vec::new();
    dfs(k, n, 1, &mut res, &mut temp);
    res
}