Sum-it-up problem

#1

import java.util.;
import java.lang.;
import java.io.*;

/* Name of the class has to be “Main” only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
int arr[] = {1,1,2,5,6,7,10};
int t = 8;
sumItUp(arr,8,"",0);
}
public static void sumItUp(int[] arr, int amount, String ans, int lastIndex) {

	if (amount == 0) {
		System.out.println(ans);
		return;
	}

	for (int i = lastIndex; i < arr.length; i++) {

			sumItUp(arr, amount-arr[i], ans + arr[i] + " ", i + 1);
		
		}


	}

}
it is printing 2 times the same thing
how to solve

#2

your code logic is partially correct.
this is the approach :

  • Sort the array(non-decreasing).
  • First remove all the duplicates from array.
  • Then use recursion and backtracking to solve the problem.
      1. If at any time sub-problem sum == 0 then add that array to the result (vector of vectors).
      1. Else if sum if negative then ignore that sub-problem.
      1. Else insert the present array in that index to the current vector and call the function with sum = sum-ar[index] and index = index, then pop that element from current index (backtrack) and call the function with sum = sum and index = index+1