Doubt-Sum It Up

#1

I dont understand why we have used this condition
(“i==lastIndex || arr[i] != arr[i - 1])” in the code given below

public static void main(String args[]) {

	Scanner s = new Scanner(System.in);

	int n = s.nextInt();

	int arr[] = new int[n];

	boolean[] index = new boolean[n];

	for (int i = 0; i < n; i++) {

		arr[i] = s.nextInt();

	}

	Arrays.sort(arr);

	int amount = s.nextInt();

	sumItUp(arr, 0, amount, "", 0, index);
}

public static void sumItUp(int[] arr, int amount, int tar, String ans, int lastIndex, boolean[] index) {

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

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

		amount += arr[i];
		if (amount <= tar && (i == lastIndex || arr[i] != arr[i - 1])) {
			// if (amount >= arr[i]) {
			// index[i] = true;
			sumItUp(arr, amount, tar, ans + arr[i] + " ", i + 1, index);
			// index[i] = false;
		}
		amount = amount - arr[i];

	}
}

}

link:https://ide.codingblocks.com/s/582607

#2

Hey Shadil Farooqui,
As mentioned in the problem statement, we need to find all the unique combinations in the array. In order to do that we need to to ignore the same elements for every level of backtracking ( Consider one for loop as a level ).

We can always include the first element of for loop in order to generate all the possible distinct combinations. This condition is maintained by i == lastIndex.

As mentioned above, that we can use only distinct elements in every for loop, we compare the present element with it’s previous element, if the previous element is same we can assume that we have already calculated the result for that number. This condition is maintained by arr[i] != arr[i - 1].

#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.