关于算法:数组总和III

数组总和 III

题目

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

只应用数字 1 到 9
每个数字 最多应用一次
返回 所有可能的无效组合的列表。该列表不能蕴含雷同的组合两次，组合能够以任何程序返回。

示例 1：

输出: k = 3, n = 7
输入: [[1,2,4]]
解释:
1 + 2 + 4 = 7
没有其余合乎的组合了。

示例：

输出: k = 3, n = 9
输入: [[1,2,6], [1,3,5], [2,3,4]]
解释:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
没有其余合乎的组合了。

问题剖析

在这道题目当中咱们须要从 1 - 9 几个数两头抉择固定数目的数据去组合失去一个指定的后果。很显然这是一个组合问题，个别组合问题咱们都能够应用回溯算法进行求解，在本篇文章当中咱们次要通过介绍两种在回溯问题当中比拟罕用的分析方法，上面咱们应用这两种分析方法去剖析这个题目。

解法剖析

解法一：抉择和不抉择

首先咱们先升高一下这个数据的要求，咱们要在 1 - 3 之间进行抉择，指定数据的个数和相加之和。在这个问题当中对于每一个数据来说咱们都用两种抉择：将这个数据放入求和列表当中或者不将其放入求和列表当中。因而咱们能够画出如下的求解树（对于每一个数据都有选和不选两种状况，每一层是针对一个具体的数据）：

如上图所示，第一层示意对数据 1 进行抉择，第二层示意对数据 2 进行抉择，第三层示意对数据 3 进行抉择。每一个节点都会有两个分支，因为对应着抉择和不抉择，因而咱们结构的树是一个齐全二叉树。

当初咱们的问题是，咱们在遍历的时候，在什么条件下应该停下来。

• 第一种状况是当数据的和等于指定的值而且数据个数相等的必定须要停下来，因为这个曾经满足条件了，咱们也不须要往里面持续退出数据了，因而咱们在这样的节点的时候应该要进行递归。
• 第二种状况是如果咱们在遍历的时候，以后列表当中数据的个数加上前面所的数据的时候，数据个数还有余 k 的时候咱们也须要听下来，因为持续遍历没有意义，即便把前面的数据全副放入列表也不符合条件了，因而没有持续遍历子树的必要了。
• 第三种状况是，当咱们抉择的数据个数大于 k 的时候咱们须要进行递归，因为咱们只能抉择 k 个数据。
• 第四种状况是，当咱们抉择的数据的和曾经大于指定的数据的时候也须要进行递归，因为再往列表当中退出数据的话和只会越来越大。
• 当遍历完 1 - 9 的所有数据的时候应该停下来。

依据下面的剖析咱们能够写出如下代码：

java 代码

import java.util.ArrayList;
import java.util.List;

public class LeetCode216 {private List<List<Integer>> ans = new ArrayList<>();
  private List<Integer> path = new ArrayList<>();

  public List<List<Integer>> combinationSum3(int k, int n) {backTrace(k, n, 1, 0);
    return ans;
  }

  public void backTrace(int k, int n, int cur, int curSum) {
    // 当满足条件的时候将失去的后果退出到最终的答案当中
    if (curSum == n && path.size() == k) {ans.add(new ArrayList<>(path));
      return;
    }
    // 在这里判断上文谈到的几个递归进行条件
    if (cur >= 10 || path.size() > k || curSum > n
            || (path.size() + (10 - cur) + 1) < k) return;
    // 抉择数据
    path.add(cur);
    curSum += cur;
    backTrace(k, n, cur + 1, curSum);
    // 上面两行代码进行回溯过程
    curSum -= cur;
    path.remove(path.size() - 1);
    // 不抉择数据
    backTrace(k, n, cur + 1, curSum);
  }
}

解法二：遍历抉择

在上一个办法当中咱们的分析方法是每一个数据都有两种抉择方法选和不选。在接下来咱们要探讨的分析方法是应用组合的观点去进行剖析。下图是咱们的剖析过程失去的树。

首先咱们来剖析一下这个树是怎么生成的：

首先从待抉择的数据当中进行遍历抉择造成一个分支，而后分支可能抉择的数据就是从这个数据往后的数据，比方对于第一个分支来说它抉择了数据 1，而他前面的数据是 [2, 3]，因而他的子分支只可能从[2, 3] 当中抉择数据。对于第二个分支来说，它抉择了 2，他前面的数据只有 [3] 了，因而他只可能从 3 当中抉择数据。如此进行递归上来就失去了下面谈到的树。

从第一层到第二层变动的时候，第一个分支示意所有蕴含 1 的组合，第二个分支示意所有蕴含 2 的组合，第三个示意所有蕴含 3 的分支。然而这种说法是不够精确的，精确的来说第一个分支也有蕴含 2 的组合，蕴含 3 的组合，第 2 个分支也有蕴含 3 的组合，更精确的来说是前 n 个分支有数据 n 的所有组合。因而下面的树结构和递归形式可能组合出所有的数据。

当初咱们的工作就是须要用代码将下面的这颗树生成进去，具体代码如下：

C++ 代码

class Solution {
    vector<vector<int>> ans;
    vector<int> path;
public:
    vector<vector<int>> combinationSum3(int k, int n) {backtrace(k, n, 1, 0);
      return ans;
    }

    void backtrace(int k, int n, int cur, int curSum) {
      // 如果满足要求则将最终的数据退出到返回的答案当中
      if (curSum == n && path.size() == k) {ans.push_back(path);
        return;
      }
      // 这里就是下面谈到的递归终止条件
      if (cur >= 10 || path.size() >= k || n <= curSum || (path.size() + (10 - cur) + 1) < k)
        return;
      // 遍历每一个数据产生对应的分支 
      for (int i = cur; i <= 10 - (k - path.size()); ++i) {path.push_back(i);
        curSum += i;
        // 产生子树
        backtrace(k, n, i + 1, curSum);
        // 上面两行进行回溯操作
        curSum -= i;
        path.pop_back();}
    }
};

总结

在本篇文章当中次要给大家介绍了组合问题 III，次要用两种不同的形式去解决这个问题，第一个种解法更加容易了解一些，然而递归的深度更深，第二种办法尽管了解起来更加简单，然而递归的深度是比第一种办法小的，空间复杂度更低。

以上就是本篇文章的所有内容了，我是LeHung，咱们下期再见！！！更多精彩内容合集可拜访我的项目：https://github.com/Chang-LeHu…

关注公众号：一无是处的钻研僧，理解更多计算机（Java、Python、计算机系统根底、算法与数据结构）常识。