代码编织梦想

今天是对于之前的问题改进

1.k个数求和

对于前面 k 个数的和的求法,我们除了可以用上面的 DFS 方法以后,还有一种搜索策略。

之前的方法是每次去抉择是否选择第 
i 个数,现在我们的策略是从剩下的数中选择一个数。比如有 
5 个数 1,2,3,4,5,如果选择了 
1,那么剩下 2,3,4,5 四个数;如果选择了 2,那么剩下 1,3,4,5 四个数,还可以选择 3....;选择 
4....;选择 5.....。

代码实现起来很简单,我们标记每个数的是否被选择了。我们用 s 表示选出来的数的和,cnt 表示选出来的数的个数。

int n, k, sum, ans = 0, a[110];
bool xuan[110]; // 标记是否选择了
void dfs(int s, int cnt) {
    if (cnt == k) {
        if (s == sum) {
            ans++;
        }
    }
    for (int i = 0; i < n; i++) {
        if (!xuan[i]) {
            xuan[i] = true;
            dfs(s + a[i], cnt + 1);
            xuan[i] = false;
        }
    }
}

去除重复的方案

如果 int a[5] = {1, 2, 3, 4, 5}; 当 k=6 时,根据我们的方法可以获得:1 2 3

1 3 2
2 1 3
2 3 1
3 1 2
3 2 1


6 种选择方案,但是它们本质上是一种 1 + 2 + 3,所以可以尝试去除重复的方案。

仔细观察可以发现,它找出的 66 种方案实际上是 1, 2, 3 的全排列,而 n 个数进行全排列时,方案数有 n!=1×2×⋯×n 种。

所以 dfs 计算出来的方案数 ans 还需要除以 n!。

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/2303_79457186/article/details/136092931

算法训练营day22, 回溯2-爱代码爱编程

216. 组合总和 III func combinationSum3(k int, n int) [][]int {   //存储全部集合   result := make([][]int, 0)   //存储单次集合   path := make([]int, 0)   var backtrace func(k int, n int, s

【算法】{画决策树 + dfs + 递归 + 回溯 + 剪枝} 解决排列、子集问题(c++)-爱代码爱编程

文章目录 1. 前言2. 算法例题46.全排列78.子集 1. 前言 dfs问题 我们已经学过,对于排列、子集类的问题,一般可以想到暴力枚举,但此类问题用暴力解法 一般都会超时,时间开销过大。

基础数学问题整理-爱代码爱编程

    最近刷了一些关于基础数学问题的题目,大致是关于组合数、分解质因数还有一些思维题,题目来自洛谷的【数学1】基础数学问题 - 题单 - 洛谷,很多思路还是之前没有见过的,都是简单到一般难度的题目(橙、题、绿题),特别做个整理。 目录 组合数问题 编号 组合数问题  分解质因数 Hankson 的趣味题 细胞分裂  思维题

java-爱代码爱编程

目录  一.  二分查找(递归): 代码详解: 运行结果: 二分查找优化: 优化代码:  运行结果(返回对应查找数字的下标集合):  ​编辑  二分查找(非递归): 二. 插值查找  代码详解: 运行结果:  三. 斐波那契[黄金分割查找] 代码详解:  运行结果:  一.  二分查找(递归): 前提条件: 所要

【nicn的刷题日常】之打印整数二进制的奇数位和偶数位-爱代码爱编程

  目录 1.题目描述  2.解题思路  3.解题     1.题目描述  获取一个整数二进制序列中所有的偶数位和奇数位,分别打印出二进制序列 2.解题思路  1. 提取所有的奇数位,如果该位是1,输出1,是0则输出0 2. 以同样的方式提取偶数位置  检测num中某一位是0还是1的方式:    1. 将num

代码随想录算法训练营第24天(回溯2)| 216.组合总和iii & 17.电话号码的字母组合-爱代码爱编程

回溯的总结: 树的深度(递归的层数) 树的深度就是要取的数据的个数,通过path的size判断是否收集到足够的数据 树的宽度(循环的范围) 输的宽度就是搜索的范围,就是for循环的循环范围,这个范围可以做剪枝操作 递归和回

力扣344-爱代码爱编程

反转字符串 题目链接 解题思路 双指针算法两个指针向中间靠拢,直至相遇交换两个指针的值 class Solution { public: void reverseString(vector<

14 归并排序和其他排序-爱代码爱编程

1.归并排序 2.计数排序 1. 归并排序 基本思想 建立在归并操作上的一种排序算法,采用分治法的一个典型应用。将已有序的子序列合并,得到完全有序的序列,将两个有序表合成一个称为二路归并。 原数组无序,以中间分割为

排序算法-爱代码爱编程

原创不易,转载请注明出处。欢迎点赞收藏~ 插入排序是一种简单直观的排序算法,它的基本思想是将待排序的元素分为已排序和未排序两部分,每次从未排序部分中选择一个元素插入到已排序部分的合适位置,直到所有元素都插入到已排序部分,完成排序。 具体的插入排序算法如下: 从第一个元素开始,将其视为已排序部分。取出下一个未排序元素,在已排序部分从后往前扫描

【leetcode】37. 解数独(困难)——代码随想录算法训练营day30-爱代码爱编程

题目链接:37. 解数独 题目描述 编写一个程序,通过填充空格来解决数独问题。 数独的解法需 遵循如下规则: 数字 1-9 在每一行只能出现一次。数字 1-9 在每一列只能出现一次。数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。(请参考示例图) 数独部分空格内已填入了数字,空白格用 '.' 表示。 示例 1: 输入:

(52)只出现一次的数字iii-爱代码爱编程

文章目录 每日一言题目解题思路代码结语 每日一言 十年磨一剑,风雨未曾阻挡;愿你乘风破浪,不负韶华时光。 题目 题目链接:只出现一次的数字 给你一个整数数组 nums,其中恰好有两个元

【算法训练营】数字盒子,重编码,成绩排序(python实现)-爱代码爱编程

数字盒子 问题描述 你有一个盒子,你可以往里面放数,也可以从里面取出数。 初始时,盒子是空的,你会依次做 Q 个操作,操作分为两类: 插入操作:询问盒子中是否存在数 x,如果不存在则把数 x 丢到盒子里。删除操作:询问盒子中是否存在数 x,如果存在则取出 x。 对于每个操作,你需要输出是否成功插入或删除。 输入格式

p1026 [noip2001 提高组] 统计单词个数-爱代码爱编程

题目传送门 题目描述 给出一个长度不超过 200 的由小写英文字母组成的字母串(该字串以每行 20 个字母的方式输入,且保证每行一定为 20 个)。要求将此字母串分成 k 份,且每份中包含的单词个数加起来总数最大。 每份中包含的单词可以部分重叠。当选用一个单词之后,其第一个字母不能再用。例如字符串 this 中可包含 this 和 is,选用 thi