一道小巧的编程难题（高手进，请教思路）

现有整型数组{1，2，4，3，5，8}，写出一个函数，找出所有和为10的集合。

227 个解决方案

#1

方法1：将数组排序，然后从两端分别向前推进，伪代码如下：
      while(end > start)
      {
           if(intArray[start] + intArray[end] == 10){output; start++; end--;}
           else if(intArray[start] + intArray[end] > 10) { end-- ;}
           else { start++;}
      }
方法2：用辅助数组k[]，初始化为0.遍历一次这个整形数组，把数组元素大小作为下标，k[intArray[i]]=1,实现初始化辅助数组，当查找时再遍历一次，如看到第二个元素2，因为k[2]=1,只需要看k[8]是否为1，为1说明8也存在，输出，为0，说明8不存在

#2

想到一个思路。
找到 >= N/2 的数，然后分为 2组，然后从大的数组里面取一个出来，
然后再从小的里面用 >=(N-big1)/2 , 分为2组，以此类推

#3

一楼的没法求出 2+3+5 = 10这种情况
本题数据不多 暴力搜吧

#4

2L正解
1先排序，再二分查找复杂度为O(NlgN)+O(N)
2是类哈希 复杂度为O（n）不过浪费空间复杂度              
其实就是2L说的两种  

#5

。。看错题了，可以用先排序后递归的方法 
paixu(num);
void  solve(int* num,int sum,chain<int> result)
{ 
if(sum>0&&num!=null)
{ 
 solve(num+1,sum,result);
 result.addnode(num[0]);
 solve(num+1,sum-num[0],result);
}
else
if(sum==0)
{result.show();}
else
return;

}

#6

就是子集树嘛

private static void subSetOfTree(int n, int result) {
	if (n == a.length) {
		if (result == 10)
			output();
		return;
	}
	for (int i = 0; i < 2; i++) {
		subSetOfTree(n + 1, result + i * a[n]);
	}
}

#7

背包问题, 如果是整数的话用DP吧.

#8

先排序，然后从大到小递归，
比如你这个题，
最大是8，
-依次遍历比8小的，加起来超过10的跳过
-到2的时候匹配，返回一条结果
-然后是1，和是9，再次递归，但1以下没有了，于是结束8的递归
然后是5，
-5以下第一个是4，和不超过10，再次递归，直到1，匹配，返回一条结果
-再下来是3，和不超过10，再次递归，直到2，匹配，返回一条结果
。。。

#9

我不知道

#10

带剪枝的子集和算法

#11

可归结为背包或者子集数搜索问题。
背包的话：DP或者回溯均可。

大致写了个回溯的版本

#include <stdio.h>
#include <stdlib.h>
#define N 100
int x[N];

void output(int * a,int n){
	for(int i = 0;i<n;i++){
		//printf("%d ",x[i]);
		if(x[i]){
			printf("%d ",a[i]);
		}
	}
	printf("\n");
}

void subSet(int k,int n,int sum,int a[]){
	if(k==n){
		if(sum == 0){
			output(a,n);
		}
		return;
	}
	for(int i=0;i<=1;i++){
		x[k] = i;
		sum -= a[k]*x[k];
		subSet(k+1,n,sum,a);
		sum += a[k]*x[k];
	}
}

main(){
	int s[7] = {1,2,3,4,5,6,7};
	subSet(0,7,10,s);

}
/*
 *{4,6},   {3,7},   {2,3,5},   {1,3,6 },   {1,4,5},   {1,2,7},  {1,2,3,4}
 *
 **/

#12

写错一点点：

    for(int i=0;i<=1;i++){
        x[k] = i;
        sum -= a[k]*x[k];
        subSet(k+1,n,sum,a);
    }

#13

我有一种思路，但不知道对不对：
依次从数组中剔除0，1，2，3，5个元素，对剩余的元素使用哈夫曼编码：
（1）从数组中剔除0个元素，实际上还是原来的数组，对原来的数组使用哈夫曼编码，直到生成的节点的值为10停止；
（2）从数组中剔除一个元素，该情况有6中子情况（因为数组有6个元素），都要考虑。这里假设剔除了第一个元素，则对剩余的5个元素用哈夫曼编码，直到生成的节点的值为10停止；
（3）从数组中剔除2个元素，对剩余的4个元素采用哈夫曼编码，直到生成的节点的值为10停止；（从6个元素的数组中剔除两个元素要要用排列组合的知识，所有情况都要考虑到）。
...
(5)从数组中剔除5个元素，对剩余的一个元素采用哈夫曼编码（还是它本身），直到生成的节点的值为10止；

这样就可以保证找到的和为10的元素子集不重不漏（我感觉应该可以，不知道大家认不认同）。

但这种方法的计算量比较大。

这只是我的想法，不一定对，请大家指正。

#14

用python写的，排序就不写了，排序的作用可以尽快结束递归
a = (1, 2, 3, 4, 5, 8)
aim = 10

def make(a, aim, b):
        num = len(a)
        if 0 == num:
                return
        for i in range(num):
                c = list(b)
                sub_aim = aim - a[i]
                c.append(a[i])
                if sub_aim == 0:
                        print c
                elif sub_aim > 0:
                        if num > i + 1:
                                make(a[(i + 1):], sub_aim, tuple(c))

b = []
make(a, aim, b)

#15

a = (1, 2, 3, 4, 5, 8)
aim = 10

def make(a, aim, b):
        num = len(a)
        if 0 == num:
                return
        for i in range(num):
                c = list(b)
                sub_aim = aim - a[i]
                c.append(a[i])
                if sub_aim == 0:
                        print c
                elif sub_aim > 0:
                        if num > i + 1:
                                make(a[(i + 1):], sub_aim, tuple(c))

b = []
make(a, aim, b)

用源代码方式重新贴一次

#16

和下面这道题是一样的

题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=1258

题意：给定一个t,n,和n个数字，求出n个数字中若干个数之和等于t的情况，按不递增顺序输出这些数字，
明显是 dfs ,因为要遍历所有的情况，所以搜索的时候不能返回，又要求按不递增顺序输出，只要保证这n个数是按不递增排列的
就能保证搜索的时候是按不递增搜索的，当然题目以及已知输入的n个数是不递增的。
注意回溯，还有跳过相同的，避免重复搜索。

代码：

#include<iostream>
#include<cstring>
using namespace std;
int v[15],t,n,path[15],flag,vis[15],cnt;
void dfs(int cur,int sum){
	 if(sum==t){
		 flag=1;
		 printf("%d",path[0]);
		 for(int i=1;i<cnt;i++)
			 printf("+%d",path[i]);
		 puts("");
	 }
	 for(int i=cur;i<n;i++){
		  if(!vis[i] && sum+v[i]<=t){
			   vis[i]=1;
			   path[cnt++]=v[i];
			   dfs(i+1,sum+v[i]);
			   vis[i]=0;//回溯
			   cnt--; //
			   while(i+1<n && v[i+1]==v[i]) //跳过相同的
				  i++;
		  }
	 }
}
int main(){
	int i;
	while(scanf("%d%d",&t,&n)==2 && t+n){
		 for(i=0;i<n;i++)
			 scanf("%d",&v[i]);
		 printf("Sums of %d:\n",t);
		 flag=cnt=0;
		 for(i=0;i<n;i++)
			 if(v[i]<=t)
				 break;
		 memset(vis,0,sizeof(vis));
		 dfs(i,0);
		 if(!flag)
			 puts("NONE");
	}
return 0;
}

#17

这个可以看成一个背包吧。要放好一个大小为10的包。。

#18

//2011年10月21日17:28:51
//功能：背包问题（非递归算法，利用栈保存，并包含栈的各种操作）

#include <stdio.h>

typedef struct
{
int s[10];
int top;
}Stack;

//全局变量声明
Stack B;
int w[6]={1, 2, 4, 3, 5, 8},bao = 10;

void init(Stack * B)
{
B->top=0;
}

void push(Stack * B,int k)
{
B->s[B->top]=k;
++(B->top);
}

void traverse(Stack B)
{
int temp=B.top-1;
printf("(");
for(; temp>=0; temp--)
{
printf("%d",w[B.s[temp]]);
if(temp != 0)
printf(",");
}
printf(")\n");
}

int pop(Stack * B)
{
--(B->top);//注意删除栈顶元素并返回时，使top减1，此时栈顶元素被删除，但top所指向的即为栈顶元素，因为定义时top指向栈顶下一个元素
return B->s[B->top];
}

bool empty(Stack B)
{
if(B.top == 0)
return 1;
else
return 0;
}

int main(void)
{
int k=0;

init(&B);
do{
while(bao>0 && k<6)
{
if(bao-w[k] >= 0)
{
push(&B,k);
bao-=w[k];
}
k++;
}
if(bao == 0)
traverse(B);
k=pop(&B);
bao+=w[k];
k++;
}while( !( (k==6) && empty(B) ) );//注意do...while循环最后分号不能少；并且是当while里表达式为真时，继续执行do...while,否则退出循环

return 0;
}

/*
在vc++6.0中的运行结果为：
---------------------------------
(3,4,2,1)
(5,4,1)
(5,3,2)
(8,2)
---------------------------------
*/

#19

好像是个多项式求解的问题呀！
1*x1 + 2*x2 + 4*x3 + 3*x4 + 5*x5 + 8*x6 = 10 .
其中Xi=0或Xi=1 ，找到满足Xi=1的组合就能找到解呀。

#20

1 2 4 3 5 8
可以直接输出。

#21

//暴力求解一下
/*
compile : gcc -lstdc++ -lm main.cpp
*/

#include<cstdio>
#include<cmath>
using namespace std ;

void print_result( int nNumberCount , int array[] , int sum ) ;

int main( int argc , char* argv[] )
{
    int D[] = { 1 , 2 , 4 , 3 , 5 , 8 , 65 , 32 , 14 , 34} ;
    int num_count = sizeof(D)/ sizeof(D[0]) ;
    print_result( num_count , D , 70 ) ;
    return 0 ;
}

void print_result( int nNumberCount , int A[] , int sum )
{
    const int M = nNumberCount ;
    long x = 2 , y = M ;
    long result = pow( x , y ) ;
    const int N = (int) result  ; 
    const int RESULT = sum ;
    int B[N] ;
    int C[M] ;

    for( int index = 0 ; index < N ; ++ index ) 
    {
    B[index] = index ;
    }

    for( int n = 0 ; n < N ; ++ n )
    {
        int result = 0 ;
        for( int index = 0 ; index < M ; ++ index )
        {
            int temp = B[n] ;
            C[index] = (temp >> index) & 1 ;
            temp = C[index] * A[index] ;
            result += temp ;
        }

        if( result == RESULT )
        {
            for( int m = 0 ; m < M ; ++ m )
            {
                if( C[m] == 1 ) 
                    printf( "%d\t" , A[m] ) ;
            }
            printf( "\n" ) ;
        }
    }   
}

//result  as follow :
/*
1 4 65
2 3 65
5 65
4 32 34
1 3 32 34
2 4 3 5 8 14 34
*/

#22

枚举子集之后不断判断就可以了..

#23

这个题目，在程序员书中有见过,主要是考察所有的排序组合

#24

《编程之美》上原题，这个太简单了。。。

#25

问题的实质一定要看明白，否则回了这道题，下一道又不会了。这个问题其实就是有1元，2元，5元，10元，20元的钞票，问能组合成100元的所有情况，这种题前两天在这个论坛我刚看到，今天又出来了。哎，大家最好还是先搜一下问题的答案比较好，散这么多分干嘛啊？

#26

该回复于2012-05-14 08:45:43被版主删除

#27

这是代码：
package com.zuheq;

public class ZuheMian {

/**
 * @param args
 */
public static void main(String[] args) {
ZuheMian.getAllKinds();
}
public static void getAllKinds(){
int a=1,b=2,c=3,d=4,e=5,f=8;
int ai=0,bi=0,ci=0,di=0,ei=0,fi=0;
System.out.println("所有可能成为10的组合");
System.out.println("1,2,3,4,5,8分别是：");
for(ai=0;ai<=1;ai++){
for(bi=0;bi<=1;bi++){
for(ci=0;ci<=1;ci++){
for(di=0;di<=1;di++){
for(ei=0;ei<=1;ei++){
for(fi=0;fi<=1;fi++){
if(ai*1+bi*2+ci*3+di*4+ei*5+fi*8==10){

// System.out.println("1有："+ai+",2有"+bi+",3有"+ci+",4有"+di+",5有"+ei+",8有"+fi);
System.out.println(ai+","+bi+","+ci+","+di+","+ei+","+fi);
}
}
}
}
}
}
}
}
}


打印：

所有可能成为10的组合
1,2,3,4,5,8分别是：
0,1,0,0,0,1
0,1,1,0,1,0
1,0,0,1,1,0
1,1,1,1,0,0

那个帖子还有高人给出了一种算法，效率比这个高，但是本人没看懂，
有兴趣可以看看，那个帖子高人很多

#28

看了下楼上各位的代码只有19楼的哥们我比较认同，其他的还扯什么排序，搞不懂。这个问题和我提到的100元的问题不同之处就是结果是子集，也就是每个数字智能出现0或1次，比那个100元的问题循环少了，实质还是一样的。

#29

遍历一次树子集就可以了

等价于求方程组

x1*1+x2*2+....=10
x1=0 || 1
x2=0 || 1
.
.
.


的解集

#30

引用 14 楼  的回复:

用python写的，排序就不写了，排序的作用可以尽快结束递归
a = (1, 2, 3, 4, 5, 8)
aim = 10

def make(a, aim, b):
        num = len(a)
        if 0 == num:
                return
        for i in range(num):
           ……

那样太麻烦了，可以这样写

from itertools import combinations

def select_sub_list(alist):
    select_list = [j for i in xrange(len(alist)) for j in combinations(alist,i) if sum(j) == 10]
    return list(set(select_list))

print select_sub_list([1,2,4,3,5,8,10])

#31

子集数  学习了

#32

6L正解。。。

#33

呵呵，有点意思

#34

和下面这道题是一样的

题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=1258

题意：给定一个t,n,和n个数字，求出n个数字中若干个数之和等于t的情况，按不递增顺序输出这些数字，
明显是 dfs ,因为要遍历所有的情况，所以搜索的时候不能返回，又要求按不递增顺序输出，只要保证这n个数是按不递增排列的
就能保证搜索的时候是按不递增搜索的，当然题目以及已知输入的n个数是不递增的。
注意回溯，还有跳过相同的，避免重复搜索。

#35

该回复于2012-05-13 21:59:22被版主删除

#36

引用 27 楼  的回复:

这是代码：
package com.zuheq;

public class ZuheMian {

/**
* @param args
*/
public static void main(String[] args) {
ZuheMian.getAllKinds();
}
public static void getAllKinds(){
int a=1,b=2,c=……

这我能说课本迫害到你了么

#37

该回复于2012-05-13 21:49:15被版主删除

#38

用回溯吧
 private void find(List<int> source, List<int> sum)
        {
            if (source.Sum() == 10)
            {
                output(source);
            }
            else if (source.Sum() > 10)
                return;
            for (int i = 0; i < sum.Count; i++)
            {
                if (!source.Contains(sum[i]))
                {
                    source.Add(sum[i]);
                    find(source, sum);
                    source.Remove(sum[i]);
                }
            }
        }
        private void output(List<int> source)
        {
            for (int i = 0; i < source.Count-1; i++)
            {
                if (source[i] > source[i + 1])
                    return;
 
            }
            foreach (int s in source)
            {
                label1.Text += s + ",";
            }
            label1.Text = label1.Text.Substring(0, label1.Text.Length - 1) + "\r\n";
        }
        private void Form2_Load(object sender, EventArgs e)
        {
            label1.Text = "";
            System.Collections.Generic.List<int> sum = new List<int>() { 1, 2, 4, 3, 5, 8 };
            find(new List<int>(), sum);
        }

#39

该回复于2012-05-13 21:51:25被版主删除

#40

深度问题！只能支持一下！

#41

#include <stdio.h>
#include <stdlib.h>
#define MAX 6

const int endSum = 10; // 所得出的和为10
int a[] = {1, 2, 4, 3, 5, 8};
int mask[] = {0, 0, 0, 0, 0, 0};

void printNumber()
{
	for ( int i=0; i<MAX; ++i )
	{
		if ( 1==mask[i] )
			printf("%d ", a[i]);
	}
	puts("");
}

void fun(int index, int remain, int maxCount)
{
	if ( 0==maxCount && 0==remain )
	{
		printNumber();
		return ;
	}      
	//end the recursion
    if ( index == MAX )
	{
		return ;
	}

	else
	{
          for ( int i=index; i<MAX; ++i )
		  {
			  mask[i] = 1;
              fun( i+1, remain-a[i], maxCount-1 );
			  mask[i] = 0;
		  }
	}
}



int main()
{
	for ( int i=1; i<MAX+1; ++i )
	{
        fun(0, 10, i);    
	}
	return 0;
}

递归枚举~

#42

算法分析里面有相似算法

#43

现有整型数组{1，2，3，4，5，8}，写出一个函数，找出所有和为10的集合。

用我的思路very easy

//{1，2，3，4，5，8}
// 1，2，3，4，5，6

public static void doit()
{
	StringBuilder sb = new StringBuilder();
	StringBuilder sbNode = new StringBuilder();
	int[] source=new int[] {1,2,3,4,5,8};
	string stringData = "111111";//表示有6个数！
	int intData = Convert.ToInt32(stringData,2);
	int sum;

	for (int i = intData; i > 0; i--)
	{
		 sum = 0;
		int buff = i;
		sbNode.Remove(0, sbNode.Length);
		for (int length = 0; buff > 0; length++)
		{
			if ((buff & 0x00000001) != 0)
			{
				sum += source[length];
				sbNode.Append(source[length].ToString() + "\t");

			}
			buff = buff >> 1;
		}
		//此次是不是符合条件？并记录结果
		if (sum == 10)
		{
			sb.AppendLine(sbNode.ToString());
		}
	}
	MessageBox.Show(sb.ToString(), "结果" + Convert.ToString(intData,2) + "系列");
}

结果：





--ok;

#44

该回复于2012-05-13 21:55:34被版主删除

#45

该回复于2012-05-13 21:55:35被版主删除

#46

不错，很强大。。。

#47

从大到小排 ，要然后在加。

#48

很不错，给力~！~！~

#49

该回复于2012-05-14 08:35:11被版主删除

#50

如果不需要考虑性能，暴力即可：

int n[6] = {1,2,3,4,5,8};
void Find(int a,int s,char x[100])
{
	char y[100];
	for(int i=a;i<6;i++)
	{
		if(s + n[i] < 10)
		{
			sprintf(y,"%s + %d",x,n[i]);
			Find(i + 1 ,s + n[i],y);
		}
		if(s + n[i] == 10)
			printf("%s + %d = 10\r\n",x,n[i]);
	}
}
Find(0,0,"");

输出：

 + 1 + 2 + 3 + 4 = 10
 + 1 + 4 + 5 = 10
 + 2 + 3 + 5 = 10
 + 2 + 8 = 10