jyanchus
BAN USER@xyz,
There are two recursive examples in these answers that implement this go left(-), go right(+), tree approach. Mine a few above and nasim's right below. Likewise, several of the iterative approaches do the same. It's naturally a tree as the root node is array element 0 and there are two paths to each of the subsequent elements.
Working recursive example:
public static void printSumExp(int[] nums,int target){
if(nums.length == 0) return;
pseRecurse(nums,target-nums[0],String.valueOf(nums[0]),1);
}
public static void pseRecurse(int[] nums,int target,String s, int idx){
if(idx == nums.length){
if(target == 0){
System.out.println(s);
}
return;
}
pseRecurse(nums,target-nums[idx],s+" + "+nums[idx],idx+1);
pseRecurse(nums,target+nums[idx],s+" - "+nums[idx],idx+1);
}
TEST:
printSumExp(new int[]{1,9,1,2,1,2,3,6},9);
OUTPUT:
1 + 9 + 1 + 2 + 1 - 2 + 3 - 6
1 + 9 + 1 - 2 + 1 + 2 + 3 - 6
1 + 9 + 1 - 2 - 1 - 2 - 3 + 6
1 + 9 - 1 + 2 - 1 + 2 + 3 - 6
1 + 9 - 1 - 2 + 1 - 2 - 3 + 6
TEST (per example in question):
printSumExp(new int[]{1,9,1,2},9);
OUTPUT:
1 + 9 + 1 - 2
I went down this road also and I wanted to like this solution. Unfortunately, it falls apart and gets cumbersome if array.length and rotate amount share common divisors (length = 9, rotate=3;length = 8, rotate=4; length = 8, rotate=2; ...)
- jyanchus June 12, 2015I think that the triple reverse method is the way to go, provided the reverse logic is mature and runs in O(n/2) by swapping outer limits iterating in to mid.