博客

一、问题描述

给定一个数t，以及n个整数，在这n个数中找到加和为t的所有组合，例如t=4，n=6这6个数为[4,3,2,2,1,1]，这样输出就有4个不同的组合它们的加和为4:4,3+1,2+2,and 2+1+1。请设计一个高效算法实现这个需求。

二、解题思路

先将数据按从小到大进行排序，然后使用回溯法遍历所有可能。注意去掉重复的结果。

三、Java代码实现

//--------------------- Change Logs----------------------
// <p>@author weiwei.han Initial Created at 2015-9-25<p>
//-------------------------------------------------------

/**
 *求任意一个数组中所有和为给定数的组合个数
 */
public class CombinationCount {

    private static int count = 0;
    private static int []array = {0, 9, 8, 3, 4, 1, 2, 7, 5, 6};
    private static int sum = 8;
    
    static int getCount() {
        CombinationCount.quickSort(array, 0, array.length-1);
        CombinationCount.sum(array.length-1);
        return count;
    }
    
    private  static int[] sum(int n) {
        if(n == 0){
            return new int[]{array[0]};
        }
        
        int length = (int)Math.pow(2, (n+1))-1;
        int a[] = new int[length];
        int b[] = sum(n-1);
        
        int i=0;
        for(i=0; i<(length-1)/2; i++) {
            a[i] = b[i];
            int temp = b[i] + array[n];
            if(temp == sum){
                count++;
            }
            a[i+(length+1)/2] = temp;
        }
        if(array[n] == sum) {
            count++;
        }
        a[(length-1)/2] = array[n];
        
        return a;
    }
    
    private static void quickSort(int []array, int left, int right) {
        if(left >= right) {
            return;
        }
        int q = pagenation(array, left, right);
        quickSort(array, left, q-1);
        quickSort(array, q+1, right);
    }
    
    private static int pagenation(int []array, int left, int right) {
        int i=left, j=right+1;
        int p = (int)Math.random()*(right-left+1)+left;
        swap(array,left, p);
        int x = array[left];
        
        while(true) {
            while(i<right && array[++i] < x);
            while(j>left && array[--j] > x);
            if(i > j) {
                break;
            }
            swap(array,i,j);
        }
        return j;
    }
    
    private static void swap(int [] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
    
    public static void main(String[] args) {
        //CombinationCount.sum(array.length-1);
        //System.out.println(CombinationCount.count);
        System.out.println(CombinationCount.getCount());
    }
    
}