LeetCode216.组合总和lll

4.组合总和lll(LeetCode216)

题目叙述:

找出所有相加之和为 nk 个数的组合,且满足下列条件:

  • 只使用数字1到9
  • 每个数字 最多使用一次

返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次,组合可以以任何顺序返回。

示例 1:

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

示例 2:

输入: 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
没有其他符合的组合了。

示例 3:

输入: k = 4, n = 1
输出: []
解释: 不存在有效的组合。
在[1,9]范围内使用4个不同的数字,我们可以得到的最小和是1+2+3+4 = 10,因为10 > 1,没有有效的组合。

提示:

  • 2 <= k <= 9
  • 1 <= n <= 60

思路:

1.回溯函数的参数以及返回值

  • 没有返回值

  • 我们需要startindex变量来标志着我们遍历的位置

  • 并且需要一个一维数组path来存放当前的结果,一个二维数组result来存储最终的结果集。

  • targetSum(int)目标和,也就是题目中的n。

  • k(int)就是题目中要求k个数的集合。

  • sum(int)为已经收集的元素的总和,也就是path里元素的总和。

  • startIndex(int)为下一层for循环搜索的起始位置。

代码如下:

vector<vector<int>> result;
vector<int> path;
void backtracking(int targetSum, int k, int sum, int startIndex)

2.回溯函数的结束条件

  • 当我们数组中的元素个数等于k时,就收集到了k个元素,也就是我们满足题目的条件,此时就应该返回了
  • 并且,如果此时的targetSum=sum了,就是满足我们题目要求的一个答案,我们就应该收集这个答案了。

代码如下:

if(path.size()==k){
    if(sum==targetSum) result.push_back(path);
    return;
}

3.单层递归的逻辑

  • 此处我们是选择1-9的九个数字,因此单层递归的for循环应该是≤9
for(int i=startindex;i<=9;i++)
  • 处理过程就是 path收集每次选取的元素,相当于树型结构里的边,sum来统计path里元素的总和

  • 并且,我们还需要有回溯的过程,只要加了的话,我们要回到上一层,重新选择的话,此时我们就应该减回来

代码如下:

for(int i=startindex;i<=9;i++){
    path.push_back(i);
    sum+=i;
    //此时这里是i+1,因为元素不能够重复取
    backtracking(targetSum,k,sum,i+1);
    //这里是回溯的逻辑,在之前加过的元素,如果我们要回溯到上一层再操作,就要减回来
    sum-=i;
    path.pop_back();
}
  • 其实,我们也不需要对sum做加减的操作,直接对传入的参数进行操作,这样相当于是将回溯的逻辑隐藏在了递归函数中,不推荐这种做法。
for(int i=startindex;i<=9;i++){
    path.push_back(i);
    //此时这里是i+1,因为元素不能够重复取
    backtracking(targetSum,k,sum+i,i+1);
    path.pop_back();
}

代码:

  • 我们根据上面三步的分析,不难得出代码:
class Solution {
public:
    vector<int> path;
    vector<vector<int>> result;
    void backtracking(int targetSum, int k, int startindex, int sum) {
        if (path.size() == k) {
            if (sum == targetSum)
                result.push_back(path);
            return;
        }
        for (int i = startindex; i <= 9; i++) {
            sum += i;
            path.push_back(i);
            backtracking(targetSum, k, i + 1, sum);
            //回溯的过程
            path.pop_back();
            sum -= i;
        }
    }
    vector<vector<int>> combinationSum3(int k, int n) {
        //从1开始选
        backtracking(n, k, 1, 0);
        return result;
    }
};

剪枝:

  • 在这段代码中,我们可以有两个剪枝的过程。
  1. 第一就是如果我们发现当前的sum已经大于targetSum了,那么我们就没有必要就再往下进行遍历了,肯定没有符合条件的k个数相加为n。
    void backtracking(int targetSum, int k, int startindex, int sum) {
        //发现sum已经大于targetSum了,直接结束本层递归
        if(sum>targetSum) return;
        if (path.size() == k) {
            if (sum == targetSum)
                result.push_back(path);
            return;
        }
        for (int i = startindex; i <= 9; i++) {
            sum += i;
            path.push_back(i);
            backtracking(targetSum, k, i + 1, sum);
            //回溯的过程
            path.pop_back();
            sum -= i;
        }
    }
  1. 第二就是单层递归的条件,我们没有必要从startindex遍历到9,只需要遍历到9-(k-path.size())+1即可
  • 为什么只需要遍历到9-(k-path.size())+1就可以了呢?这题的逻辑其实和我们之前讲解的LeetCode77组合总和有异曲同工之妙,我们数组中的元素个数为path.size()个,我们还需要选择k-path.size()个元素
  • 又因为我们是从i开始,树的最底层,也就是递归的深度,是遍历到9结束,那么这个区间内的元素个数必须≥k-path.size()
  • 这个区间的元素个数为:9-i+1,那么9-i+1>=k-path.size(),可以推出i<=9-(k-path.size())+1,就是说i至多从这个位置开始遍历

剪枝过程图如下:

热门相关:纣临   邪王追妻99次:娘子,等我   帝少夜宠:小甜妻,乖!   重生之大文豪   末日乐园