首页 > 其他分享 >回溯 组合问题(二)

回溯 组合问题(二)

时间:2022-10-11 23:23:24浏览次数:84  
标签:return 组合 int sum 问题 targetSum 回溯 path

题目描述:

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

只使用数字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
没有其他符合的组合了。

思路

组合给定,求和与k个数的组合,也相当于树的宽度给定,求树的深度;
依然使用“回溯”三步来求值;

返回值与参数

本题除了全局变量result以及存储个数的path,还需要相加之和的目标和targetSum,以及个数k,还有
每个数相加的和sum,以及为下一层for循环搜索的位置参数startIndex;

void backtracking(int targetSum,int k,int sum,int startIndex)

确定终止条件

终止条件就是在path大小到整棵树的叶子,也就是等于k值,还得考虑这k个数的组合与目标和相等;

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

递归函数以及回溯

横向遍历依然是for循环搜索;

void backtracking(int targetSum,int k,int sum,int startIndex)
{    

    if(path.size()==k){ //终止条件
    if(sum==targetSum) result.push_back(path);
    return;
    }

    for(int i = startIndex;i<=9;i++)
    {
        sum += 1;
        path.push_back(i);
        backtracking(targetSum,k,sum,i+1); //参数为i+1,到下一层递归
        sum -= 1; //回溯
        path.pop_back(); //回溯
    }

}

剪枝优化

如果所选元素之和已经打过目标值得和,那就没有必要继续往下递归;

if(sum > targetSum) {
    return; //剪枝操作
}

另外,之前得思路,就是对于for循环得范围也可以剪枝干,i<=9-(k-path.size())+1

全部代码

class Solution {
private:
   vector<vector<int>> result; //存放结果集
   vector<int> path;//存放符合条件的结果
   void backtracking(int targetSum,int k,int sum,int startIndex)
   {
       if(sum > targetSum)
       {
           return;
       }
       if(path.size()==k){
           if(sum == targetSum) result.push_back(path);
           return; //如果path.size()==k但是sum!=targetSum,则直接返回
       }
       for(int i=startIndex;i<=9-(k-path.size())+1;i++)
       {
           sum += i;
           path.push_back(i);//处理
           backtracking(targetSum,k,sum,i+1);
           sum -= i;
           path.pop_back();//回溯
       }
   }
public:
    vector<vector<int>> combinationSum3(int k, int n) {
      backtracking(n,k,0,1);
      return result;
    }
};

小结

此题其实与昨天得题目,都有类似得地方,对于我来说,难度在于剪枝优化for循环范围的处理,这部分确实还需要反复琢磨。

标签:return,组合,int,sum,问题,targetSum,回溯,path
From: https://www.cnblogs.com/7xiaomao/p/16782984.html

相关文章

  • 记录一次解决登录失败问题的方法与思路
    记录解决登录失败问题的方法与思路背景今天同组的小伙伴搭建了一套微服务测试环境.9个服务器分为多个组总入口有一个Nginx服务器.连接共同的redis,nacos,rabbitmq......
  • centos7出现yum之类的问题的时候可能是加入的一些源导致的问题最佳的解决方案就是-loo
    //傻逼的我胡搞出现不知道添加什么软件源到/etc/yum.repo中结果出现了一堆错-搜了很长时间没解决-算了-返璞归真(回到初始的状态)吧,看了一下别人的阿里云的服务器中初始的时候......
  • CSV文件\ufeff问题
    今天用C++写TopN问题使用堆排序读取excel转成CSV文件中的数据std::stringstreamss;std::stringtemp;floatdata;std::ifstreamdatafile("filepath/to/csv")getline......
  • C++ 栈和典型迷宫问题
    1.前言栈是一种受限的数据结构,要求在存储数据时遵循先进后出(LastInFirstOut)的原则。可以把栈看成只有一个口子的桶子,进和出都是走的这个口子(也称为栈顶),封闭的另一端称......
  • yml问题
    YML的问题:当配置其他的生产环境,后面的配置文件不会生效下面的ok.haha无法加载......
  • 一个有意思的分钱模拟问题
    大家好,我是吴师兄,今天来分享一个有意思的分钱模拟问题,为了帮助大家理解,采取了可视化的方式。这个问题描述是这样的:房间里有100个人,每人都有100元钱,他们在玩一个游戏。每......
  • 【图论——第七讲】Pirm算法求最小生成树问题及其堆优化
    文章目录​​一、前言​​​​二、Pirm算法求最小生成树​​​​三、Pirm算法堆优化​​​​最后​​一、前言最小生成树定义:一个有n个结点的连通图的生成树是原图的极小......
  • 10.7 上课问题的讨论与思考
    一、动手实验:继承条件下的构造方法调用继承的语法:class子类名extends父类名{......}  父类(parentclass)和超类(superclass)两者通常指直接上级基类(baseclass)......
  • 第一行代码3:ContentProvider问题
    在providertest项目中查询databasetest项目的数据库出现问题Failedtofindproviderinfoforcom.example.databasetest.providerjava.lang.IllegalArgumentException:......
  • 容器并不能解决一切问题
    容器化在开发和运维领域掀起了一场风暴。在过去,部署是高度依赖于特定技术的,通常需要对每个项目进行大量不可重复的工程工作。你是否部署到VPS?你是否在分发虚拟机镜像?静态可......