public class Test {
public static void main(String[] args) {
int[] arr = {1,2,4,6,9};
List<Integer> lst = new ArrayList<Integer>();
new Test().add(arr, 20, 5, lst);
}
/**
* @param arr 目標數組
* @param target 需要求和的值
* @param index 這個參數最為重要，這是為了保證消除重復遍歷的情況，能夠極大限度減少遍歷次數
* @param cur 當前保存的路徑
* */
public void add(int[] arr, int target ,int index, List<Integer> cur){
if( target < getMin(arr))
return;
else{
for(int i = index-1 ; i >= 0 ; i -- ){
if(arr[i] == target){
for(Integer o : copyAndAdd(cur,arr[i]))
System.out.print(o + ",");
System.out.println();
//輸出等於20的路徑
}
else{
add(arr, target-arr[i], i+1 , copyAndAdd(cur,arr[i]));
}
}
}
}
//深拷貝壹份list,並將新的node加入路徑之中
public List<Integer> copyAndAdd(List<Integer> lst, int item){
List<Integer> cur_t = new ArrayList<Integer>();
cur_t.addAll(lst);
cur_t.add(item);
return cur_t;
}
public int getMin(int[] arr){
int k = Integer.MAX_VALUE;
if(null == arr || arr.length < 1)
return k;
for(int i = 0; i < arr.length; i++ ){
if(arr[i] < k)
k = arr[i];
}
return k;
}
}