Here is a structured summary of everything you’ve studied so far
regarding recursion for subset, subsequence, combination, and
permutation generation — including code patterns, intuition, time
complexity, and critical follow-up questions with answers.
1. Subset Generation
Definition: All possible combinations of elements from the set, including the
empty set and the full set.
Recursive Pattern:
void generateSubset(int index, int[] arr, List<Integer> current,
List<List<Integer>> result) {
if (index == [Link]) {
[Link](new ArrayList<>(current));
return;
}
// Include current
[Link](arr[index]);
generateSubset(index + 1, arr, current, result);
// Exclude current
[Link]([Link]() - 1);
generateSubset(index + 1, arr, current, result);
}
Time Complexity: O(2^n)
Intuition: Binary decision tree (pick / not pick at each index)
2. Subsequence Generation
Definition: Subsets with preserved order (derived by skipping or including
elements in sequence).
Same code and logic as subset generation
Time Complexity: O(2^n)
Note: For strings, it’s often used for pattern matching or DP problems.
3. Combination (choose k elements)
Definition: Select k elements from a set of n, where order does not matter
and elements are not reused.
Recursive Pattern:
void generateCombination(int index, int[] arr, int k,
List<Integer> current, List<List<Integer>> result) {
if ([Link]() == k) {
[Link](new ArrayList<>(current));
return;
}
for (int j = index; j < [Link]; j++) {
[Link](arr[j]);
generateCombination(j + 1, arr, k, current, result);
[Link]([Link]() - 1);
}
}
Time Complexity: O(C(n, k)) where C(n, k) = n! / (k!(n-k)!)
Intuition: Pick or skip each element, avoid choosing earlier elements again
4. Permutation (all orderings)
Definition: All possible orderings of elements. Order matters. No element is
reused.
Visited-array based Pattern:
void generatePermutations(int[] arr, boolean[] visited,
List<Integer> current, List<List<Integer>> result) {
if ([Link]() == [Link]) {
[Link](new ArrayList<>(current));
return;
}
for (int j = 0; j < [Link]; j++) {
if (!visited[j]) {
visited[j] = true;
[Link](arr[j]);
generatePermutations(arr, visited, current, result);
[Link]([Link]() - 1);
visited[j] = false;
}
}
}
Time Complexity: O(n!)
Alternative Pattern (swap-based):
void permuteInPlace(int[] arr, int index, List<List<Integer>>
result) {
if (index == [Link]) {
[Link](copy(arr));
return;
}
for (int j = index; j < [Link]; j++) {
swap(arr, index, j);
permuteInPlace(arr, index + 1, result);
swap(arr, index, j);
}
}
Use: Efficient, no extra space for visited
5. k-Permutations
Definition: All permutations of length k from a set of n values.
Change in base case:
if ([Link]() == k) {
[Link](new ArrayList<>(current));
return;
}
Time Complexity: O(P(n, k)) = n! / (n - k)!
6. Combinations with Repetition
Not yet covered — but in this version, you can reuse elements and order
doesn’t matter.
Recursive signature changes slightly: Instead of j + 1, you use j again in
the recursive call to allow reuse.
Follow-Up Questions and Answers
Q1: Why don’t we use j + 1 in permutations like we do in
combinations?
A: Because in permutations we care about order and want to try every
position. In combinations, we avoid duplicates by skipping used indices
using j + 1.
Q2: How do we handle duplicates in permutations?
A:
1. Sort the array first.
2. Skip duplicates in the loop using:
if (j > 0 && arr[j] == arr[j - 1] && !visited[j - 1])
continue;
Q3: How can we generate permutations of size k?
A: Change the base case to:
if ([Link]() == k) {
[Link](new ArrayList<>(permutation));
return;
}
Q4: Why does swap-based permutation work without
visited[]?
A: Because every position i is fixed with all possible remaining values j via
swapping. The swap ensures that all unique arrangements are explored in-
place, and recursive depth ensures no reuse.
Q5: How many total permutations of size k from n
elements?
A: P(n, k) = n! / (n - k)!
Q6: Why do we use .size() for List and .length for arrays
in Java?
A: .length is a property of arrays, .size() is a method of the List
interface. Mixing them causes compile-time errors.
Would you like a PDF or printable version of this for quick review?