Scribd
Upload
29 views1 page

Recursive Combination Sum Algorithm

The document contains a Java class 'Solution' that implements a method to find all unique combinations of numbers from a given array that sum up to a specified target. It uses a recursive approach to explore possible combinations and stores valid results in a list. The main method 'combinationSum' initializes the process and returns the list of combinations.

Uploaded by

wedok26771
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
29 views1 page

Recursive Combination Sum Algorithm

The document contains a Java class 'Solution' that implements a method to find all unique combinations of numbers from a given array that sum up to a specified target. It uses a recursive approach to explore possible combinations and stores valid results in a list. The main method 'combinationSum' initializes the process and returns the list of combinations.

Uploaded by

wedok26771
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd

class Solution {

// functions to fine the combinations


private void findCombinations(int ind, int arr[], int target,
List<List<Integer>> ans, List<Integer> ds)
{
// check weather arr length and index equal or not
if(ind==[Link]){
if(target==0)
{
[Link](new ArrayList<>(ds));
}
return;
}
// check the current index element of array is less equal to target or not
if(arr[ind]<= target){
// add element into the arraylist
[Link](arr[ind]);
// do recursive call for the same index element
findCombinations(ind, arr, target-arr[ind],ans, ds);
// remove last inserted element from the array list
[Link]([Link]()-1);

}
// do recursive call for the next index element
findCombinations(ind+1, arr, target,ans, ds);
}

public List<List<Integer>> combinationSum(int[] candidates, int target) {


// ans list to storing the answer
List<List<Integer>> ans= new ArrayList<>();
// call the findcombination function
findCombinations(0,candidates,target,ans, new ArrayList<>());
// return the final list
return ans;
}
}

You might also like