求数组中和为给定数的所有组合

我就是我 2023-06-14 14:56 28阅读 0赞

import java.util.Arrays;
    
    public class Test { 
    	public static void main(String[] args) { 
    		String str = "6,2,7,3,8,1,9,4";
    		double sum = 12;
    		diguiSum(str, sum);
    	}
    
    	public static void diguiSum(String str, double sum) { 
    		String[] x = str.split(",");
    		double[] array = arrayTransform(x);
    		for (int i = 0; i < 100; i++) { 
    			double[] cache = new double[i + 1];
    			int ceng = -1;
    			int cengQuit = i;
    			int startPiont = 0;
    			cir(ceng, cengQuit, startPiont, array, cache, sum);
    		}
    	}
    
    	// 递归求结果
    	public static void cir(int ceng, int cengQuit, int startPiont,
    			double[] array, double[] cache, double sum) { 
    		ceng++;
    		for (int i = startPiont; i < array.length; i++) { 
    			cache[ceng] = array[i];
    			if (ceng == cengQuit) { 
    				if (getSum(cache) == sum) { 
    					printcache(cache);
    				}
    				if (getSum(cache) > sum) { 
    					break;
    				}
    			}
    			if (ceng < cengQuit) { 
    				startPiont = i + 1;
    				cir(ceng, cengQuit, startPiont, array, cache, sum);
    			}
    		}
    	}
    
    	// 获取组合数字之和
    	public static double getSum(double[] cache) { 
    		double sum = 0;
    		for (int i = 0; i < cache.length; i++) { 
    			sum = sum + cache[i];
    		}
    		return sum;
    	}
    
    	// 打印组合的可能
    	public static void printcache(double[] cache) { 
    		for (int i = 0; i < cache.length; i++) { 
    			System.out.print(cache[i] + ",");
    		}
    		System.out.println();
    	}
    
    	// 转换数组类型 且为提高效率做准备
    	public static double[] arrayTransform(String[] strArray) { 
    		int length = 0;
    
    		double[] array = new double[strArray.length];
    		for (int i = 0; i < strArray.length; i++) { 
    			array[i] = Double.valueOf(strArray[i]);
    		}
    		Arrays.sort(array);
    		for (int i = 0; i < array.length; i++) { 
    			if (array[i] > 100) { 
    				length = i;
    				break;
    			}
    		}
    		double[] dest = new double[length];
    		if (length == 0) { 
    			return array;
    		}
    		System.arraycopy(array, 0, dest, 0, length);
    		return dest;
    	}
    }

输出结果为：

3.0,9.0,
    4.0,8.0,
    1.0,2.0,9.0,
    1.0,3.0,8.0,
    1.0,4.0,7.0,
    2.0,3.0,7.0,
    2.0,4.0,6.0,
    1.0,2.0,3.0,6.0,