日期:2014-05-20  浏览次数:20758 次

数组问题 求数组 子类和 等于N问题 求各牛人答案
例如 int []arr={1,2,3,4,3,2};

N=7;

输出结果为 
1 2 4

1 3 3

3 4


这只是个例子 

写的代码可以传参

------解决方案--------------------
背包算法的简易版。可以自行Google下。
------解决方案--------------------
Java code
package cn;

import java.util.Arrays;


public class ArrayTest {
    private int[] arr = {1,2,3,4,3,2};
    private int N = 7;
    public void fun(int... x){
        int xSum = 0;
        for(int n : x){
            xSum = n + xSum;
        }
        for(int i : arr){
            if((xSum + i) == N){
                System.out.print(i+" ");
                for(int n : x){
                    System.out.print(n+" ");
                }
                System.out.println();
            } else if(x.length <= arr.length){
                int[] tmpArr = Arrays.copyOf(x, x.length + 1);
                tmpArr[x.length] = i;
                fun(tmpArr);
            }
        }
    }
    public static void main(String[] args) {
        ArrayTest arrayTest = new ArrayTest();
        arrayTest.fun();
    }
}

------解决方案--------------------
Java code

//有些可以优化。讲究用着吧
public class Test2 {
    public static void main(String[] args) throws Throwable {
        Set<List<Integer>> sets = new HashSet<List<Integer>>();
        int[] arr = {1,2,3,4,3,2};
        int number= 7;
        int n = arr.length;
        int[] num = new int[n]; //声明一个长度为n的数组
        for (int i=0; i<num.length; i++)
        {num[i] = 0;} //初始化数组的n个元素都是0
        while (num[0] < 2) {
            int sum =0;
            for (int i=0; i<num.length; i++){
                sum+=arr[i]*num[i];
            }
            if(sum == number){
                List<Integer> list = new ArrayList<Integer>();
                for (int i=0; i<num.length; i++){
                    if(num[i]==1) list.add(arr[i]);
                }
                Collections.sort(list);
                sets.add(list);
            }
            num[num.length-1]++; //模拟进位,低位增加
            for (int i=num.length-1; i>0; i--) { //判断是否发生进位
                if (num[i] == 2) { //如果某位到达2,则发生进位
                    num[i] = 0; //进位就是该位置重新赋值为1
                    num[i-1]++; //该位置的前一位置增加1
                }else{
                    break;
                }
            }
        }
System.out.println(sets);
        }
 }