Given an array of integers and number N, Write an algorithm to find and print all the subsets of the array for which sum is equal to N.
Java Code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 | import java.util.ArrayList; import java.util.Arrays; import java.util.List; public class JavaExample { public void findSets(int [] arrA, int sum){ System.out.println("Given Array: " + Arrays.toString(arrA) + ", required sum: " + sum); Arrays.sort(arrA); List<Integer> combinationList = new ArrayList<>(); combinationUtil(arrA, sum, 0, 0, combinationList); } public void combinationUtil(int arrA[] , int sum, int currSum, int start, List<Integer> combinationList){ if(currSum==sum) { System.out.println(combinationList); return; } int prevElement = -1; for (int i = start; i <arrA.length ; i++) { if(prevElement!=arrA[i]) { if(currSum+arrA[i]>sum) //array is sorted, no need to check further break; combinationList.add(arrA[i]); combinationUtil(arrA, sum, currSum + arrA[i], i + 1, combinationList); combinationList.remove(combinationList.size() - 1); prevElement = arrA[i]; } } } public static void main(String[] args) { int [] arrA = {6,2,7,8,2,4,1,3,7,5}; int n = 8; JavaExample p = new JavaExample(); p.findSets(arrA, n); } } |
Output:
1 2 3 4 5 6 7 8 9 10 11 | Given Array: [6, 2, 7, 8, 2, 4, 1, 3, 7, 5], required sum: 8 [1, 2, 2, 3] [1, 2, 5] [1, 3, 4] [1, 7] [2, 2, 4] [2, 6] [3, 5] [8] |
