L8. Combination Sum | Recursion | Leetcode | C++ | Java

Find DSA, LLD, OOPs, Core Subjects, 1000+ Premium Questions company wise, Aptitude, SQL, AI doubt support and many other features that will help you to stay focussed inside one platform under one affordable subscription. Have a hassle free one stop solution for up-skilling and preparing.

[smitboraniya]

Sir, I have watched many youtube channels for recursion, and all of them claim that they are the best in youtube, you'll learn to think recursively, blah blah blah... But as I have started watching your playlist of recursion, I got a very clear idea about recursion. Your way of explaining with recursive trees is the best thing I found anywhere online. It just resonates with our brain and now I can think RECURSIVELY. Thank you and keep making such amazing videos..

[gowthamarun]

by doing all these i have developed logic and submitted this problem and got accepted. That was the first time, even a small problem i will make mistakes.
But now, i am improving. Thanks bhaiya for doing this and sharing your knowledge to everyone

[chitranshsaxena]

I watched the video till 7:25. It gave me an intuition of what could have been done, I explained this same approach to myself again and tried to code .... and damn ...I got the answer....
There were repeated entries in my answer set, but still not being able to code backtracking problems to actually solving one to some extent .... feels really good

[arunachalamm]

How do you identify a good teacher.. When he explains each and every step so clearly and makes his students to think towards the solution instead of typing the solution and asking them to memorise it. You are the best Striver Bhai!!!!

[cosmic_boy]

My experience :)
The first time i did the recursion, i couldn't understand what was happening, why it was happening. I was like ya Striver is saying something, i am understanding something and coding it. Mostly i would understand the solution about 40-70% only. I thought how dumb i am. But now i am doing it for the second time after 1.5 months gap. Initial recursion playlist questions, again i couldn't solve. But with few more questions, it started clicking, and now, Striver tells only the method. And i am able to code it myself ! Such an improvement !

to anyone thinking they are dumb...it feels so in the first time. but do not worry. REVISION is very important ! eventually, we it starts clicking! :)
Thank you STRIVER :)

[Ji-yoon]

It is the first time I'm able to understand recursion so clearly. Thank you so so much 💗💗

[shwetabhagat]

15:00- recursive tree
19:00-time complexity
23:34-code

[sheelaggarwal]

LeetCode: Combination Sum(39.) ->
Code:
class Solution {
public:
void helper(int i, int target, int SumTillNow, vector<int>&candidates, vector<int>&subset, vector<vector<int>>&ans){

if(SumTillNow==target){
ans.push_back(subset);
return;
}

if(SumTillNow>target) return;

if(i>=candidates.size()) return;

//pick
SumTillNow+=candidates[i];

helper(i, target, SumTillNow, candidates, subset, ans);
SumTillNow-=candidates[i];
subset.pop_back();

//not pick
helper(i+1, target, SumTillNow, candidates, subset, ans);
}


vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<int>subset;
vector<vector<int>>ans;
helper(0, target, 0, candidates, subset, ans);
return ans;
}
};

[yasiromar]

This guy made my path to learn recursion easier.The way he explain is quite commendable. Thank you brother ❤

[balajisrinivasan]

time complexity : (t ^ n) * k
reasoning : consider target is t (say 10) and array has all the elements as 1 (the worst possible case). For each index, we will have 10 options. There are totally n indices in the array. Hence processing will be done for 10 * 10 * 10... n times. So, total time will be 10 ^ n. Generalising it will be (target ^ n) * k => where k is the average size of the combination

[Eternally_Namashrita]

if we add one OR condition in the base condition as if(ind == arr.size() || target == 0), keeping rest of the code same, we get the right answer but in the less recursive calls. Because sometimes we get the target before reaching the last index, so once we get the target we need to stop at that moment and no need to check for further elements. As it's OR, once the base condition is satisfied, again inside that we need to check whether (target == 0) and confirm.

Here is the code :

public class RecursionEx
{

public static void main(String[] args)
{
Scanner in = new Scanner(System.in);
List<List<Integer>> answer;
System.out.print("Size of array : ");
int n = in.nextInt();
int[] num = new int[n];
System.out.println("array elements : ");
for(int i = 0; i < n; i++)
{
num[i] = in.nextInt();
}
System.out.print("Enter target : ");
int sum = in.nextInt();

answer = result(num, sum);
for(List<Integer> i : answer)
System.out.println(i);
}

private static void combSumk(int i, int[] num, int s, List<List<Integer>> answer, ArrayList<Integer> arr)
{
if(i == num.length || s == 0)
{

if(s == 0)
answer.add(new ArrayList<>(arr));
return;
}

if(num[i] <= s)
{
arr.add(num[i]);
combSumk(i, num, s-num[i], answer, arr);
arr.remove(arr.size()-1);
}
combSumk(i+1, num, s, answer, arr);
}

public static List<List<Integer>> result(int[] num, int target)
{
List<List<Integer>> answer = new ArrayList<>();
combSumk(0, num, target, answer, new ArrayList<>());
return answer;
}
}

[shefalijain]

You are the best. I have always found myself getting confused in recursion. But now I think I am getting it. Thank you Striver!

[coefficient]

Striver bhaiya should be in the UN protected list❤.

[Munchen]

Striver thank you very much bro 😊
All is clear. One moment: 13:00 🕐 it is valid base case if targer < nums[i] -> return

[jawadvajeeh]

You are awesome! Feeling confident in recursion now. Thanks a million!

[kunalverma]

This is the same as of unbounded knapsack along with printing all psbl combinations.

[luckydewangan]

Striver bhaiya has an another level of explanation. Understood every single words and entire approach🔥💥

[shayonchakravarty]

another lecture of recursion series ..another day of falling in love with striver's awesome explanation skill...i was like how man??!! how come someone sooo good at transfering knowledge to the community!! ❤️❤️❤️❤️🙌🙌🙌

[anmolgirdhar]

best explanation on youtube
Thankyou for the lovely content

[vvsish]

Easy approach like power set
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
res=[]
def dfs(curr, i, tot):
if tot==target:
res.append(curr.copy())
return

if i>=len(candidates) or tot>target:
return

curr.append(candidates[i])
dfs(curr, i, tot+candidates[i])

curr.pop()
dfs(curr, i+1, tot)

dfs([], 0, 0)
return res