在面试的时候我做不出来的算法题目

Question

给定一个数组和一个数total:
arr = {1,2,3,4,5,6,7,8,9,10}
total = 10;
求 从arr中任意取得N个数，使得和为total，总共有多少种取法，例如：10  1,9 2,3,5
方法原型 ：int getCombineNum(int[] arr, int total);

Answer 1

google查背包问题，思路和这差不多的。

Answer 2

我说一下思路。不知道行不行。
递归来做
｛1,2,3,4,5,6,7,8,9｝
把这个数组分解成两部分
｛a,b｝其中sum(a)<total，b是剩下的部分
例如｛1,{2,3,4,5,6,7,8,9}｝ 或者{{1,2},{3,4,5,6,7,8,9}}或{{2,4},{1,3,5,6,7,8,9}}
然后再从b中找等于total-a的数字。
递归的退出条件是当b中个数为1,此时如果sum(a) + b = total就算一个。如果不等就跳过继续
差不多这样。我没做过，也空写。大概思考一下就这样。可能有纰漏的地方，你自己再想想

Answer 3

package com.element.tech;import java.util.ArrayList;
import java.util.List;public class TestBeiBao
{
    public void getData(ArrayList<Integer> bags, int[] data, int Total)
    {
        //打印bags内容 
        int sum = 0;
        boolean flag = false;
        for (int i = 0; i < bags.size(); i++)
        {
            Integer d = bags.get(i);            System.out.print(d.toString()+ " " );
            flag = true;
        }        if (flag)
        {
            System.out.println();
        }        //在数字中循环，依次调用函数，递归结束的条件是找不到data[i] < Total的情况 
        //了        
        for (int i = 0; i < data.length; i++)
        {            if (data[i] <= Total)
            {
                ArrayList<Integer> newPuts = new ArrayList<Integer>();
                for (int j = 0; j < bags.size(); j++)
                {
                    newPuts.add(bags.get(j));
                }
                newPuts.add(Integer.valueOf(data[i]));
                getData(newPuts, datas, Total - data[i]);
            }
        }    }    public int[] datas = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };    public static void main(String[] args)
    {
        TestBeiBao p = new TestBeiBao();
        p.getData(new ArrayList<Integer>(), p.datas, 10);
    }}
可以打印出小于等于10的，楼主在过滤下 等于10的，这个是别人算法 借鉴的

Answer 4

package com.element.tech;import java.util.ArrayList;public class TestBeiBao
{
    public void getData(ArrayList<Integer> bags, int[] data, int Total)
    {
        //打印bags内容       
        int sum = 0;
        boolean flag = false;
        ArrayList<Integer> array = new ArrayList<Integer>();
        for (int i = 0; i < bags.size(); i++)
        {
            Integer d = bags.get(i);            
            sum += d;
            array.add(new Integer(d));
            flag = true;
        }        if (sum == 10)
        {
            for (int i = 0; i < array.size(); i++)
            {
                System.out.print(array.get(i) + " ");
            }
            System.out.println();
        }        //在数字中循环，依次调用函数，递归结束的条件是找不到data[i] < Total的情况              
        for (int i = 0; i < data.length; i++)
        {            if (data[i] <= Total)
            {
                ArrayList<Integer> newPuts = new ArrayList<Integer>();
                for (int j = 0; j < bags.size(); j++)
                {
                    newPuts.add(bags.get(j));
                }
                newPuts.add(Integer.valueOf(data[i]));
                getData(newPuts, datas, Total - data[i]);
            }
        }    }    public int[] datas = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };    public static void main(String[] args)
    {
        TestBeiBao p = new TestBeiBao();
        p.getData(new ArrayList<Integer>(), p.datas, 10);
    }}把等于10 全打印出来，楼主你这个需求 那些数字可以重复加吗？
如果不行 这个程序还要改改

Answer 5

谢谢各位强人的帮助！这几天没有上网，关于GGMMYQL的回复，非常感谢！但是你把题目改了，我感觉是要用递归，但是它已经把方法告诉你了，是传1个数组和一个INT类型参数，还有我可能忘记交代了，不好意思，不能重复加数字。谢谢大家！