Lesson 2 � Beginner-Intermediate

Subsets, Permutations & Combinations

Recursion se hum subsets, permutations aur combinations generate kar sakte hain. Ye patterns interview mein bahut zyada aate hain. Include/Exclude pattern samajh lo toh 70% recursion problems solve ho jayengi.

? 28 min✓ Beginner-Intermediate✓ Recursion basics

Recursion Patterns kya hain?

WHAT

Recursion patterns wo recurring templates hain jo subsets, permutations, combinations generate karne mein use hote hain. Har element pe ek decision lena hota hai � include karo ya exclude karo. Ye decision tree recursion se banta hai.

WHEN

Jab tumhe saare possible subsets/chunks chahiye, jab order matter kare (permutations), jab order matter na kare (combinations), jab power set generate karna ho � tab ye patterns use karo.

WHERE

Subsets I & II, Permutations I & II, Combinations, Combination Sum, Power Set, Letter Combinations � ye sab is pattern se solve hote hain.

Mental Model: Imagine karo tumhare paas [1, 2, 3] hain. Har number ke saath ek decision hai � "is number ko apne set mein shamil karun ya nahi?" Ye ek binary tree banta hai � left branch = include, right branch = exclude. Recursion is tree ko traverse karta hai.

Pattern 1: Subsets (Include/Exclude)

Subsets generate karna recursion ka sabse fundamental pattern hai. Har element ke liye 2 choices hain � include karo ya exclude karo. 2^n subsets bante hain n elements ke liye:

# Subsets of [1, 2, 3]
# Decision tree:
# []
# / \
# [1] []
# / \ / \
# [1,2] [1] [2] []
# / \ / \ / \ / \
# [1,2,3][1,2][1,3][1] [2,3][2] [3] []

def subsets(nums, i=0, current=[]):
 if i == len(nums):
 print(current)
 return
 # Include nums[i]
 subsets(nums, i + 1, current + [nums[i]])
 # Exclude nums[i]
 subsets(nums, i + 1, current)

subsets([1, 2, 3])

Output: [], [3], [2], [2,3], [1], [1,3], [1,2], [1,2,3] � total 2^3 = 8 subsets. Har level pe 2 choices hain � isliye exponential time hota hai.

Pattern 2: Permutations

Permutations mein order matter karta hai. [1,2,3] aur [3,2,1] alag permutations hain. Har position pe kaunsa element aaye � ye decide karna hota hai:

# Permutations of [1, 2, 3]
# Har position pe koi bhi unused element aa sakta hai

def permutations(nums, current=[], used=None):
 if used is None:
 used = [False] * len(nums)
 
 if len(current) == len(nums):
 print(current)
 return
 
 for i in range(len(nums)):
 if not used[i]:
 used[i] = True
 permutations(nums, current + [nums[i]], used)
 used[i] = False # Backtrack

permutations([1, 2, 3])

# Alternate approach: Swap-based permutation
def permutations_swap(nums, start=0):
 if start == len(nums):
 print(nums[:])
 return
 
 for i in range(start, len(nums)):
 nums[start], nums[i] = nums[i], nums[start] # Choose
 permutations_swap(nums, start + 1) # Explore
 nums[start], nums[i] = nums[i], nums[start] # Unchoose

permutations_swap([1, 2, 3])

Pattern 3: Combinations

Combinations mein order matter nahi karta � [1,2] aur [2,1] same hain. Sirf k elements choose karne hain n mein se:

# Combinations of n elements taken r at a time
def combinations(nums, r, start=0, current=[]):
 if len(current) == r:
 print(current)
 return
 
 for i in range(start, len(nums)):
 current.append(nums[i])
 combinations(nums, r, i + 1, current)
 current.pop() # Backtrack

combinations([1, 2, 3, 4], 2)

Key Difference: Permutations mein har element kisi bhi position pe aa sakta hai. Combinations mein order fix hota hai � sirf elements choose karte hain without repetition. Permutations = n! / (n-r)!, Combinations = n! / (r! * (n-r)!)

Include/Exclude Pattern ka Template

# Universal Include/Exclude Template
def solve(nums, i=0, current=[]):
 # Base case: sab elements process ho gaye
 if i == len(nums):
 # current = ek valid subset/permutation
 process(current)
 return
 
 # CHOICE 1: Include nums[i]
 current.append(nums[i])
 solve(nums, i + 1, current)
 current.pop() # UNCHOOSE � backtrack
 
 # CHOICE 2: Exclude nums[i]
 solve(nums, i + 1, current)

def process(current):
 print(current)

Duplicates handle karna: Subsets II

Agar array mein duplicates hain toh duplicate subsets generate honge. Sort karo aur same elements ko skip karo:

# Subsets II � with duplicates
def subsets_unique(nums):
 nums.sort() # Pehle sort karo
 result = []
 
 def backtrack(start, current):
 result.append(current[:])
 for i in range(start, len(nums)):
 if i > start and nums[i] == nums[i-1]:
 continue # Skip duplicate
 current.append(nums[i])
 backtrack(i + 1, current)
 current.pop()
 
 backtrack(0, [])
 return result

print(subsets_unique([1, 2, 2]))

Try it: code khud likho

Exercise

Question: [1, 2, 3] ke kitne permutations hain✓ Sirf number daalo.

Question: [1, 2, 3, 4] ke kitne subsets hain✓ Sirf number daalo.

Common mistakes

Backtrack nahi karna: Include ke baad current.pop() ya equivalent cleanup zaroor karo. Nahi toh galat subsets/permutations banenge.
Duplicate handling bhool jaana: Subsets II mein sort + skip duplicate zaroor karo. Nahi toh same subset baar baar aayega.
Permutation vs Combination confusion: Permutations mein order matter karta hai (har position pe koi bhi element). Combinations mein sirf elements choose karte hain (start index se).
Base case galat likhna: Subsets mein base case = sab elements process. Combinations mein base case = r elements choose ho gaye. Dono alag hain.
Index management: Subset mein i+1 se start karo. Permutation mein used[] array se track karo kaunsa element use ho chuka hai.

Lesson complete?

Patterns samajh aa gaye✓ Ab backtracking framework seekhte hain � ye patterns ko systematic banata hai aur pruning add karta hai.