LeetCode 77 | Combinations | Backtracking Algorithm Explained (Java + Debugging)

Running Time: O(N!/K!(N-K)!)
Space Complexity: Same as run time

The description reads:
"Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

You may return the answer in any order.

Example 1:

Input: n = 4, k = 2
Output:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
Example 2:

Input: n = 1, k = 1
Output: [[1]]"

Always be pluggin:

[scholarway]

We don't count the answer as part of the space complexity. We use The extra space here for ans and the recursion call stack. The depth of the call stack is equal to the length of ans, which is limited to k. Therefore: Space complexity: O(k)

[wanify]

Thanks for the explanation, btw i really paused my video when you said hold on i think its my dog TWICE lol

[HenggaoCai]

For iteration, you can create a table and keep track of what the loop prints out.

[stevefidarci]

This was a tough one. Good explanation

[wooseyoung]

Your code is so concise and it is very easy to understand, for the backtracking, I think you can draw a tree to illustrate it.

[soldiers]

hello sir my name is jaswinder singh i am from india punjab i am not able to solve the code of a combination will you help me

[SamRamezanli]

A candidate would not pass an interview with the amount of explanation you provided.

You were just coming up with stuff out nowhere without any proper explanation how and why. This is not acceptable during an actual interview.