文档章节

深度优先搜索的用法——求数组部分和

自由的角马
 自由的角马
发布于 2015/01/10 13:55
字数 438
阅读 48
收藏 1

深度优先搜索的用法——求数组部分和

 

问题主题:求数组部分和

问题描述:

给定整数a1,a2, … an,判断能否从中选出若干个数,使得它们的和为k。

限制条件:

1<=n<=20

-108<=ai<=108

-108<=k<=108

样例:

输入

n=4

a={1,2,4,7}

k=13

输出

Yes (13=2+4+7)

输入

n=4

a={1,2,4,7}

k=15

输出

    No

 

 

【解法一】

解题分析:

    用递归的方法实现深度优先搜索,从a0开始依次判断,决定ai加入或不加入,对每一个种组合进行判断,决定是否存在和为k的情况。

程序实现:

 

C++

#include "stdafx.h"

#include "iostream"

 

using namespace std;

 

const int MAX = 10;

int     result;

int a[MAX];

int sum = 0;

 

bool resolve(int a[], int n, int i, int sum) ;

 

int _tmain(int argc, _TCHAR* argv[]) {

         int n;

         cout << "?º?¨?n¨ª¨¢?Ì?䨮?:" <<endl;

         cin >> n >> result;

         cout << "?º?¨?n?ºy:" <<endl;

         for(int i=0; i<n; i++) {

                   cin >> a[i];

         }

         if(resolve(a, n, 0, sum))

                   cout << "Yes" <<endl;

         else

                   cout << "No" << endl;

         return 0;

}

 

bool resolve(int a[], int n, int i, int sum) {

         if(i >= n)

                   return sum == result;

         //??a[i]

         if(resolve(a, n, i+1, sum))

                   return true;

         //¨®¦?a[i]

         if(resolve(a, n, i+1, sum+a[i]))

                   return true;

         return false;

}

 

Java

/**
 * User: luoweifu
 * Date: 14-1-7
 * Time: 上午11:33
 */
public class PartSum {
    private int array[];
    private int result;
    public PartSum() {
 
    }
 
    public PartSum(int[] array, int result) {
        this.array = array;
        this.result = result;
    }
 
       public void setArray(int[] array) {
              this.array = array;
       }
 
       public void setResult(int result) {
              this.result = result;
       }
 
       public boolean resolve(int[] array, int i, int sum) {
              int n = array.length;
              if(i >= n)
                     return sum == result;
              if(resolve(array, i+1, sum))
                     return true;
              if(resolve(array, i+1, sum+array[i]))
                     return true;
              return false;
       }
 
       public void partsumResolve() {
              if(resolve(array, 0, 0))
                     System.out.println("Yes");
              else
                     System.out.println("No");
       }
 
       public static void main(String args[]) {
              PartSum partSum = new PartSum(new int[]{1,2,4,7}, 13);
              partSum.partsumResolve();
              partSum.setResult(15);
              partSum.partsumResolve();
       }
 
}


 

算法复杂度:

    时间复杂度O(2n)

 

本文转载自:http://blog.csdn.net/luoweifu/article/details/17881295

自由的角马
粉丝 1
博文 269
码字总数 0
作品 0
文山
私信 提问
Node中的两种遍历方式-深度优先和广度优先(附Node删除文件例子进行详解)

树的基本概念 树(Tree)是 个结点的有限集, 为 时,称为空树,在任意一棵非空树中有且仅有一个特定的被称为根(Root)的结点,当 大于 时,其余结点可分为 个互不相交的有限集 、、、,其中...

2018/09/14
0
0
PHP实现二叉树的深度优先遍历(前序、中序、后序)和广度优先遍历(层次)

http://blog.csdn.net/baidu_30000217/article/details/52953127 前言: 深度优先遍历:对每一个可能的分支路径深入到不能再深入为止,而且每个结点只能访问一次。要特别注意的是,二叉树的深...

陈小龙哈
2018/06/26
0
0
考研复试系列——第四节 深度优先搜索

考研复试系列——第四节 深度优先搜索 前言 dfs:if(判断条件) //在这里进行递归的退出return;for(遍历内容) //进行遍历,例如图中访问每一个满足某一条件的节点{if(判断是否访问过以及其他题...

cassiepython
2017/03/01
0
0
图的遍历——深度优先搜索(Depth First Search)

1.深度优先搜索(Depth First Search)遍历类似于树的先根遍历,是树的先根遍历的推广。 假设初始状态是图中所有的顶点未曾被访问,则深度优先搜索可从图中某个顶点V出发,访问此顶点,然后依...

啊哈关关
2018/01/20
1K
0
php中的数组函数学习记录2

1、检查给定的键名或索引是否存在于数组中——arraykeyexists 用法:arraykeyexists($key(mixed),$input(array))返回TRUE和FALSE $inputarray=array("1"=>"java","op"=>"R","act"=>"python"......

mrmusic
2016/03/23
54
0

没有更多内容

加载失败,请刷新页面

加载更多

SpringBoot中 集成 redisTemplate 对 Redis 的操作(二)

SpringBoot中 集成 redisTemplate 对 Redis 的操作(二) List 类型的操作 1、 向列表左侧添加数据 Long leftPush = redisTemplate.opsForList().leftPush("name", name); 2、 向列表右......

TcWong
今天
5
0
排序––快速排序(二)

根据排序––快速排序(一)的描述,现准备写一个快速排序的主体框架: 1、首先需要设置一个枢轴元素即setPivot(int i); 2、然后需要与枢轴元素进行比较即int comparePivot(int j); 3、最后...

FAT_mt
昨天
4
0
mysql概览

学习知识,首先要有一个总体的认识。以下为mysql概览 1-架构图 2-Detail csdn |简书 | 头条 | SegmentFault 思否 | 掘金 | 开源中国 |

程序员深夜写bug
昨天
10
0
golang微服务框架go-micro 入门笔记2.2 micro工具之微应用利器micro web

micro web micro 功能非常强大,本文将详细阐述micro web 命令行的功能 阅读本文前你可能需要进行如下知识储备 golang分布式微服务框架go-micro 入门笔记1:搭建go-micro环境, golang微服务框架...

非正式解决方案
昨天
8
0
前端——使用base64编码在页面嵌入图片

因为页面中插入一个图片都要写明图片的路径——相对路径或者绝对路径。而除了具体的网站图片的图片地址,如果是在自己电脑文件夹里的图片,当我们的HTML文件在别人电脑上打开的时候图片则由于...

被毒打的程序猿
昨天
9
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部