Flashcards
Print all subsets with given sum
Cards in this deck (2)
- 1Input : arr[] = {2, 3, 5, 6, 8, 10} sum = 10 Output : 5 2 3 2 8 10 Input : arr[] = {1, 2, 3, 4, 5} sum = 10 Output : 4 3 2 1 5 3 2 5 4 1static void printSubsetsRec(int arr[], int i, int sum,
ArrayList p)
{
// If we reached end and sum is non-zero. We print, p[] only if arr[0] is equal to sun OR dp[0][sum], is true.
if (i == 0 && sum != 0 && dp[0][sum])
{
p.add(arr[i]);
display(p);
p.clear();
return;
}
// If sum becomes 0
if (i == 0 && sum == 0)
{
display(p);
p.clear();
return;
}
// If given sum can be achieved after ignoring, current element.
if (dp[i-1][sum])
{
// Create new vector to store path
ArrayList b = new ArrayList<>();
b.addAll(p);
printSubsetsRec(arr, i-1, sum, b);
}
// If given sum can be achieved after considering current element.
if (sum >= arr[i] && dp[i-1][sum-arr[i]])
{
p.ad - 2—static void printAllSubsets(int arr[], int n, int sum)
{
if (n == 0 || sum < 0)
return;
// Sum 0 can always be achieved with 0 elements
dp = new boolean[n][sum + 1];
for (int i=0; i p = new ArrayList<>();
printSubsetsRec(arr, n-1, sum, p);
}
//Driver Program to test above functions
int arr[] = {1, 2, 3, 4, 5};sum=10;printAllSubsets(arr, 5,10);
Information
- Description
- Flashcards on Print all subsets with given sum, created by Suhas S on 27/05/2018.
- Created by
- Suhas S
- Views
- 0
- Rating