一个看似简单的不简单问题，求高手

Question

一个数组进行分组：[1,1,2,2,4,4,1,3,2]
按照求和为5进行分组。结果为：[1,2,2],[1,4],[4，1],[3，2]
求一个算法。

Answer 1

很简单的题啊，这是对软件专业学生（当然还要有懂得.net的老师指导过的）的课堂练习。

Answer 2

最笨的初级代码，可以这样写一个递归算法：using System;
using System.Collections.Generic;
using System.Linq;namespace ConsoleApplication1
{
    class Program
    {        static void Main(string[] args)
        {
            var lst = new int[] { 1, 1, 2, 2, 4, 4, 1, 3, 2 };
            foreach (var result in Solve(lst, 5))
            {
                result.ToList().ForEach(x => { Console.Write("{0} ", x); });
                Console.WriteLine();
            }
            Console.ReadKey();
        }        static IEnumerable<IEnumerable<int>> Solve(int[] lst, int sum)
        {
            foreach (var r in lst.Where(x => x == sum))
                yield return new int[] { r };            if (lst.Length > 1)
                foreach (var r in Solve(lst.Where((x, index) => index > 0).ToArray(), sum - lst[0]))
                    yield return new int[] { lst[0] }.Concat(r);
        }
    }
}

Answer 3

可以看到，Solve算法中不过也只有两行代码而已！你说简单不简单？！

Answer 4

http://blog.csdn.net/v_JULY_v这里面都有  算法之道

Answer 5

嗯，写太快、错了，小修改一下：假设不要求一定的顺序，那么所有可能的排列就是using System;
using System.Collections.Generic;
using System.Linq;namespace ConsoleApplication1
{
    class Program
    {        static void Main(string[] args)
        {
            var lst = new int[] { 1, 1, 1, 1, 1, 1, 2, 2 };
            foreach (var result in Solve(lst, 5))
            {
                result.ToList().ForEach(x => { Console.Write("{0} ", x); });
                Console.WriteLine();
            }
            Console.ReadKey();
        }        static IEnumerable<IEnumerable<int>> Solve(int[] lst, int sum)
        {
            foreach (var r in lst.Where(x => x == sum))
                yield return new int[] { r };            if (lst.Length > 1)
                for (var i = 0; i < lst.Length; i++)
                    foreach (var r in Solve(lst.Where((x, index) => index != i).ToArray(), sum - lst[i]))
                        yield return new int[] { lst[i] }.Concat(r);
        }
    }
}

Answer 6

针对你的“特殊情况”那好写得很。
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] data = { 1, 1, 2, 2, 4, 4, 1, 3, 2 };
            int n = 5;
            var list = data.OrderByDescending(x => x).Select(x => new { g = -1, v = x }).ToList();
            int g1 = 0;
            while (list.Any(x => x.g == -1))
            {
                int t = 0;
                g1 = list.Max(x => x.g) + 1;
                while (t != n)
                {
                    var i = list.Where(x => x.g == -1 && x.v <= n - t).First();
                    t += i.v;
                    list.Add(new { g = g1, v = i.v });
                    list.Remove(i);
                }
            }
            foreach (var i in list.GroupBy(x => x.g).Select(x => string.Join(",", x.Select(y => y.v))))
            {
                Console.WriteLine(i);
            }
        }
    }
}4,1
4,1
3,2
2,2,1
Press any key to continue . . .

Answer 7

你们代码都是大量的循环
程序这么实现是最差劲的
无语
Int[] s=[1,1,2,2,4,4,1,3,2] 要和等于5 分析下。最少要二个数相加，最多四个数相加。
定义一个新的int[] newS 让int[]的元素之和等于5可以限制newS的元素个数减少循环
 

Answer 8

public static void divide(int[] data) {
Arrays.sort(data);
List<Integer> list = new ArrayList<Integer>();
int length = data.length;
for (int i = length - 1; i >= 0; i--) {
list.add(data[i]); }
int sum = 0;
for (int i = 0; i < list.size(); i++) { sum += list.get(i);
if (sum > 5) {
sum -= list.get(i); } else if (sum == 5) {
System.out.print(list.get(i) + "\n");
sum = 0;
list.remove(i);
i = -1;
} else {
System.out.print(list.get(i) + ",");
list.remove(i);
// 后一项前进一步，i应减1
i--;
}
}
}

Answer 9

改自这位老大的代码：using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
                Console.WriteLine("[1,2,2],[1,4],[4，1],[3，2]");
        }
    }
}

Answer 10

(1 + x) * (1 + x) * (1 + x^2) * (1 + x^2) * (1 + x^4) * (1 + x^4) * (1 + x) * (1 + x^3) * (1 + x^2)
展开后，x^5来源于哪些项 典型的母函数问题，呵呵

Answer 11

偶认为算法中不应出现两个以上的foreach

Answer 12

public void arithmetic1(){
int[] initialData = {1,1,2,2,4,4,1,3,2};
System.out.println("initialData : " + initialData.toString());
List<Integer> resultList = new ArrayList<Integer>();
label1:for(int i = 0 ;i < initialData.length ; i++){
int tempValue = initialData[i];
if(tempValue == 5){
resultList.add(tempValue);
System.out.println(resultList);
resultList.clear();
continue label1;
}
if(tempValue < 5){
resultList.add(tempValue);
}
for(int j=i+1; j < initialData.length && tempValue < 5;j++){
int tempValue2 = initialData[j];
if((tempValue + tempValue2) == 5){
resultList.add(tempValue2);
System.out.println(resultList);
resultList.clear();
continue label1;
}else if((tempValue + tempValue2) < 5){
resultList.add(tempValue2);
tempValue = tempValue + tempValue2;
}else{
continue;
}
}
resultList.clear();
}
}

Answer 13

土人办法：#include <stdio.h>
#include <string.h>void main()
{
int iArray[] = {1,1,2,2,4,4,1,3,2};
int temp[9];
int iIndex[9];
int sum = 0;
int count = 0;
memset(iIndex,0,sizeof(iIndex));
memset(temp,0,sizeof(temp)); //排序
for (int a = 0; a < 9; a++)
for(int b = a; b < 9; b++)
{
if (iArray[a] < iArray[b])
{
int temp = iArray[a];
iArray[a] = iArray[b];
iArray[b] = temp;
}
} for (int i = 0; i < 9; i++)
{
sum  = 0;
for(int j = i; j < 9; j++)
{
if (0 == iIndex[j])
{
sum += iArray[j];
if (5 == sum)
{
iIndex[j] = 1;
temp[count] = iArray[j];
count ++;
break;
}
else if (sum < 5)
{
iIndex[j] = 1;
temp[count] = iArray[j];
count ++;
continue;
}
else
{
sum -= iArray[j];
}
}
else
{
j ++;
}
}
} for(int k = 0; k < 9; k++)
{
printf("%d,",temp[k]);
}
return ;
}

Answer 14

#include <memory.h>
#define SUM  5
#define NL  0
 
int main(int argc, char* argv[])
{
//[1,1,2,2,4,4,1,3,2]
//先排序
//[4,4,3,2，2,2,1,1,1]
int a[]= {4,4,3,2,2,2,1,1,1};
    int tmp[9] = { 0 }; for(int j = 0; j < sizeof(a)/sizeof(int); ++j)
{
  int s = a[j];
  tmp[j] = a[j];   for(int l=j+1; l < sizeof(a)/sizeof(int); ++l)
  {
  if(a[l] == NL)
  continue;   if((s + a[l] ) > SUM)
  {
  continue;
  }
  else if((s + a[l] ) == SUM)
  {
  s += a[l];
      tmp[l] = a[l];
      a[l] = NL;
  break;
  }
  s += a[l];
  tmp[l] = a[l];
  a[l] = NL;
  }   printf("the group %d : \t",j);
  for(int k= 0; k < 9 ;k++)
  {
if(tmp[k] == 0)
continue;
printf("%d \t",tmp[k]);
  }
  printf("\n");
  memset(tmp,0,9*sizeof(int)); }
return 0;
}

Answer 15

你的意思是没学过.net的就解决不了这个问题了？

Answer 16

System.out.println("[1,2,2],[1,4],[4，1],[3，2]");

Answer 17

#include <stdio.h>
#define NUM_MAX 20
int check[NUM_MAX] = {0};
void PrintResult(int arr[],int len)
{
for (int i = 0; i < len; i++)
{
if (check[i] == 1)
{
printf("%d ",arr[i]);
}
}
printf("\n");
}void SerachSubTree(int arr[],int start,int sum,int len)
{

if (sum==0  )
{
PrintResult(arr,len);
return ;
}
else if (sum < 0)
{
return ;
}
else
{
for(int i = start;i < len; i++)
{
check[i] = 1;
sum -= arr[i];
SerachSubTree(arr,i+1,sum,len);
//back serach 
sum += arr[i];
check[i] = 0;
}
}
}int main()
{
int arr[] ={1,1,2,2,4,4,1,3,2};
SerachSubTree(arr,0,5,sizeof(arr)/sizeof(arr[0]));
return 0;
}这个是回溯算法 但是有个问题就是 出现了很多重复的 可以通过减枝来搞定 但是 似乎这个题目的剪枝难度有点 忘求你们的改进！！

Answer 18

可以利用栈去解决，不过栈的每个元素的数据结构有两个数据域，一个是表示压入栈中的元素data（从数组中遍历），另一个是表示相应的栈中元素之和sum。算法如下：
1.初始化：sum = 0；ClearStack（ST）；
2.循环：i从 1 到 n，sum+=data;push(data,sum);
    循环：j从2到n,比较sum?>5,
      a.">"情况：pop（data,sum）,sum-=data;
      b."<"情况：sum+=data,push(data,sum)
      c."=="情况：pop(data,sum),直到空，则弹出的data序列就是结果
3.输出结果，结束。大致的思路可以这样，可能有些不完善的地方，和大家多多交流~

Answer 19

可以利用栈去解决，不过栈的每个元素的数据结构有两个数据域，一个是表示压入栈中的元素data（从数组中遍历），另一个是表示相应的栈中元素之和sum。算法如下：
1.初始化：sum = 0；ClearStack（ST）；
2.循环：i从 1 到 n，sum+=data;push(data,sum);
    循环：j从2到n,比较sum?>5,
      a.">"情况：pop（data,sum）,sum-=data;
      b."<"情况：sum+=data,push(data,sum)
      c."=="情况：pop(data,sum),直到空，则弹出的data序列就是结果
3.输出结果，结束。大致的思路可以这样，可能有些不完善的地方，和大家多多交流~

Answer 20

好吧，即让你在强调就是这个数组，那就function calc (int[] arr) {
 return [1,2,2],[1,4],[4，1],[3，2];
}

Answer 21

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
typedef std::vector<int>::iterator intVecIter;
bool ValidOrder(intVecIter start,intVecIter end,int* s,int total)
{
int nSize=end-start;
int sum=0;
for(int i=0;i<nSize;i++)
{
if (*(start+i)==1)
{
sum+=s[i];
}
}
return sum==total;
}
int main()
{
int x[]={1,1,2,2,4,4,1,3,2};
int y=5;
int n=sizeof(x)/sizeof(int);
std::vector<int> vec(6);
for (int k=0;k<=n-1;k++)
{
if (n-k-2>=0)
{
fill(vec.begin(),vec.begin()+n-k-2,0);
}
fill(vec.begin()+n-k-1,vec.end(),1);
do 
{
if (ValidOrder(vec.begin(),vec.end(),x,y))
{
std::copy(vec.begin(),vec.end(),std::ostream_iterator<int>(std::cout,"\t"));
std::cout<<std::endl;
}
} while (next_permutation(vec.begin(),vec.end()));
}
system("pause");
return 0;}