第五章：寻找满足和为定值的两个或多个数-白红宇

第五章：寻找满足和为定值的两个或多个数

阅读量：4134 次

发布时间：2019-05-25

本文共 1096 字，大约阅读时间需要 3 分钟。

第一节、寻找和为定值的两个数、三个数、四个数
题目：输入一个数组和一个数字，在数组中查找两个数，使得它们的和正好是输入的那个数字。
要求时间复杂度是O(n)。如果有多对数字的和等于输入的数字，输出任意一对即可。
例如输入数组1、2、4、7、11、15和数字15。由于4+11=15，因此输出4和11。

参见：LeetCode

2.1.7

2.1.8

2.1.9

2.1.10 *

第二节、寻找和为定值的多个数

2010年中兴面试题

编程求解：

输入两个整数 n 和 m，从数列1，2，3.......n 中随意取几个数,

使其和等于 m ,要求将其中所有的可能组合列出来。

子集和问题（也是背包问题），采用回溯+剪枝

//输入两个整数 n 和 m，从数列1，2，3.......n 中 随意取几个数,  //使其和等于 m ,要求将其中所有的可能组合列出来。 //子集和问题（也是背包问题）//回溯+剪枝#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            using namespace std; #define MAX 1000bool select[MAX]={0};int N,M;void dfs(int t,int k,int r){ select[k] = true; // 选第k个数 if (t + k == M) // 若找到一个和为M，则设置解向量的标志位，输出解 { for (int i = 1; i <= k; ++i) { if (select[i]) { printf("%d ", i); } } printf("\n"); } else { // 若第k+1个数满足条件，则递归左子树 if (t + k + (k+1) <= M) { dfs(t + k, k + 1, r - k); } // 若不选第k个数，选第k+1个数满足条件，则递归右子树 if ((t + r - k >= M) && (t + (k+1) <= M)) { select[k] = false; dfs(t, k + 1, r - k); } } }int main() { N=100; M=10; int sum = (N + 1) * N /2; //1+2+3+...+N dfs(0, 1, sum); return 0; }

转载地址：http://cbvvi.baihongyu.com/

你可能感兴趣的文章