和为定值的多个数

一时失言乱红尘 2022-01-05 10:45 192阅读 0赞

给定N个数，从中找出若干个数，使得这些数的和等于sum。

## TwoSum ##

void TwoSum(int data[], unsigned int length, int sum)
    {
        std::sort(data, data + length);
        int begin = 0;
        int end = length - 1;
        while (begin < end) {
            int cur_sum = data[begin] + data[end];
            if (cur_sum == sum) {
                printf("%d %d\n", data[begin], data[end]);
                begin++;
                end--;
            } else {
                if (cur_sum < sum)
                    begin++;
                else
                    end--;
            }
        }
    }

## MultiSum ##

0-1背包问题。

void MultiSum(int data[], unsigned int length, int sum, bool flag[], int flag_size)
    {
        if (length <= 0 || sum <= 0)
            return;
        if (sum == data[length - 1]) {
            for (int i = 0; i < flag_size; i++) {
                if (flag[i] == 1)
                    printf("%d+", data[i]);
            }
            printf("%d\n", data[length - 1]);
        }
        flag[length - 1] = 1;
        MultiSum(data, length - 1, sum - data[length - 1],flag, flag_size);
        flag[length - 1] = 0;
        MultiSum(data, length - 1, sum,flag, flag_size);
    }

参考资料:

# [寻找和为定值的多个数][Link 1] #

# [k Sum][] #

转载于:https://www.cnblogs.com/gattaca/p/7820160.html

[Link 1]: https://wizardforcel.gitbooks.io/the-art-of-programming-by-july/content/02.03.html
[k Sum]: https://pobenliu.gitbooks.io/leetcode/k%20Sum.html

发表评论取消回复

表情：

评论列表（有 0 条评论，192人围观）

还没有评论，来说两句吧...

相关阅读

相关 vue绑定多个class和多个style的方式

class绑定多个 // isActive 为true就会加active的class，同理isRed <div :class="{'active':isA

悠悠/ 2022年10月07日 06:49/ 0 赞/ 170 阅读

相关在数组中寻找和为指定值的两个数

题目：在数组中寻找和为指定值的两个数，如arr=\{1, 2,3,4,7,8\} ，指定值sum为12，返回4+8=12 方法1：采用暴力破解（即穷举），时间复杂度为O(

爱被打了一巴掌/ 2022年08月27日 05:37/ 0 赞/ 169 阅读

相关寻找和为定值的多个数

输入两个整数 n 和 m，从数列1，2，3.......n 中随意取几个数, 使其和等于 m ,要求将其中所有的可能组合列出来。两种方法，其实本质都是递归算法结构

小咪咪/ 2022年08月07日 13:59/ 0 赞/ 129 阅读

相关寻找和为定值的两个数

寻找和为定值的两个数 1. 题目描述给定一个数组（无序或者有序，两种情况都要考虑），找出和为M的两个数。最多时间复杂度能有多少？ https:

比眉伴天荒/ 2022年08月06日 00:23/ 0 赞/ 156 阅读

相关为元素绑定多个响应函数

1、第一种方法 (这个方法不支持IE8及以下的浏览器!) addEventListener() // btn01.addEventListener("click",func

青旅半醒/ 2022年06月01日 04:41/ 0 赞/ 180 阅读

相关三个数的和为0

三个数的和为0 给出一个长度为N的无序数组，数组中的元素为整数，有正有负包括0，并互不相等。从中找出所有和 = 0的3个数的组合。如果没有这样的组合，输出No Solut

深碍√TFBOYSˉ_/ 2022年05月15日 04:47/ 0 赞/ 186 阅读

相关 C++中map的使用——用map解决“输出数组中和为定值的所有两（三）个数的组合”

思路：将数组中的数，按照数值—频率的形式储存到一个字典（map）中，然后对任意的键key，寻找另一个键key1 = sum - key，分三种情况，key1==key，key1

末蓝、/ 2022年05月15日 00:28/ 0 赞/ 259 阅读

相关和为定值的多个数

给定N个数，从中找出若干个数，使得这些数的和等于sum。 TwoSum void TwoSum(int data[], unsigned int length,

一时失言乱红尘/ 2022年01月05日 10:45/ 0 赞/ 193 阅读

相关寻找和为定值的多个数

编程求解：输入两个整数 n 和 m，从数列1，2，3.......n 中随意取几个数, 使其和等于 m ,要求将其中所有的可能组合列出来。 // 寻求和为

小鱼儿/ 2021年11月15日 13:18/ 0 赞/ 236 阅读

相关输入一串数字，找到其中两个数的和为某个给定值的坐标

题目：输入一串数字，找到其中两个数的和为某个给定值的坐标例子：输入一串数字如 2,8,6,7,3；找到其中两个数的和加起来等于9的坐标；显然2+7=8，那

今天药忘吃喽~/ 2021年06月24日 16:09/ 0 赞/ 307 阅读