Competitive programming or sport programming is a mind sport involving participants trying to program according to provided specifications.
Table of Contents
Recursion
Recursion is one of the most powerful and elegant tools in programming or even in competitive — but it can seem confusing at first. In this guide, you’ll learn what recursion is, how to identify recursive problems, how to approach solving them step by step, and how to build your recursive thinking muscle.
What is Recursion?
Recursion is a programming technique where a function calls itself to solve a smaller version of the original problem.
It’s like solving a puzzle by solving a smaller version of the same puzzle.
✅ If a problem can be broken down into smaller, similar subproblems, it can usually be solved using recursion.
Real-Life Analogy: Nested Boxes
Imagine you have a stack of nested boxes, each containing another smaller box, and the last one contains a gift. To get the gift:
- Open the outer box.
- Open the next box inside it.
- Keep going until you find the gift.
- Then close each box as you go back.
This is exactly how recursion works!
The Structure of a Recursive Function
Every recursive function has two main parts:
- Base Case/ Stopping criteria
- This is the simplest possible case.
- It tells the function when to stop calling itself.
- If there’s no base case, the function will call itself forever and crash.
- Recursive Case
- This is where the function calls itself with a smaller version of the problem.
def any_recursive(n):
if Stopping criteria:
return something
return some_result (operation like +,- etc or even nothing) any_recursive(n')
#Example return some_result + any_recursive(n')Practice
Example 1: Sum
Find the Sum of all numbers from 1 to n
Solution
Step 1: Whether it can be solved via recursive or not?, Can the problem be broken into smaller parts?
sum(5) => 5+sum(4) => 4+sum(3) =>3+sum(2)=>2+sum(1)=>1+sum(0)Step 2 : Stopping criteria
at sum(0), we should stop and return 0
if n==0:
return 0
Step 3: Recursive Case
return n + sum(n-1) # 5+sum(4) Code
def sum(n):
if n==0:
return 0
return n+sum(n-1)
print(sum(5)) #15Example 2: Factorial
Solution
Step 1: Whether it can be solved via recursive or not? Can the problem be broken into smaller parts
factorial(5) => 5*factorial(4)=>4*factorial(3)=>3*factorial(2)=>2*factorial(1)=>1*factorial(0)Step 2: Stopping criteria
if n==0:
return 1Step 3: Recursive Case
return n*factorial(n-1) #5*factorial(4)Code
def factorial(n):
if n==0:
return 1
return n*factorial(n-1)
print(factorial(5)) #120Example 3: Count Down
def count_down(n):
if n==0: # Base Case
return
print(n)
return count_down(n-1) # Recursive Call happens first
count_down(5)
'''
5
4
3
2
1
'''Example 4: Count Up
def count_up(n):
if n == 0: # Base Case
return
count_up(n - 1) # Recursive Call happens first
print(n) # Then we print
count_up(5)
'''
1
2
3
4
5
'''Key Difference Between the Two:
- In countdown, you print before the recursive call.
- In countup, you print after the recursive call.
Example 5: Reverse a string
Step 1 : Can the problem be broken into smaller parts?
reverse_string("hello")
= reverse_string("ello") + "h"
= reverse_string("llo") + "e" + "h"
= reverse_string("lo") + "l" + "e" + "h"
= reverse_string("o") + "l" + "l" + "e" + "h"
= "o" + "l" + "l" + "e" + "h"
= "olleh"Step 2: Stopping criteria
If the string is empty or has only one character, return it.
if len(s) <= 1:
return s
Step 2: Recursive Case
Take the first character, reverse the rest of the string recursively, and put the first character at the end.
Way 1
return reverse_string(s[1:]) + s[0]
'''
reverse_string("hello")
= reverse_string("ello") + "h"
= reverse_string("llo") + "e" + "h"
= reverse_string("lo") + "l" + "e" + "h"
= reverse_string("o") + "l" + "l" + "e" + "h"
= "o" + "l" + "l" + "e" + "h"
= "olleh"
'''Code
def reverse(s):
length = len(s)
if len(s)<=1:
return s
return s[length-1]+reverse(s[:length-1])Way 2:
return s[length-1]+reverse(s[:length-1])
'''
reverse_string("hello")
= o + reverse_string("hell")
= o + l + reverse_string("hel")
= o + l + l + reverse_string("he")
= o + l + l + e + reverse_string("h")
= "o" + "l" + "l" + "e" + "h"
= "olleh"
'''Code
def reverse_string(s):
if len(s) <= 1: # Base Case
return s
return reverse_string(s[1:]) + s[0] # Recursive CaseExample 6: Check if a string is a palindrome
Step 1: Stopping Criteria
If the string has 0 or 1 character, it’s a palindrome.
Step 2: Recursive Case
- If the first and last characters are the same, check the substring in between.
- Otherwise, it’s not a palindrome.
def palindrome(s):
if len(s)<=1:
return True
if s[0]!=s[-1]:
return False
return palindrome(s[1:-1])Example 7: Find maximum element in a list
Way 1 :
- Finding max of 0th and last index.
- Then removing last index element , repeat this
def find_max(lst):
if len(lst)==1:
return lst[0]
if lst[0]<lst[-1]:
lst[0],lst[-1] = lst[-1],lst[0]
return find_max(lst[:-1])Way 2 Better approach then way 1
def find_max(lst):
if len(lst) == 1: # Base case
return lst[0]
rest_max = find_max(lst[1:]) # Recursive call
return max(lst[0], rest_max)Drawback for way 1 and 2
- You’re modifying the list in-place, which may not be safe in all contexts.
- Slicing creates a new list every time, so it’s not the most efficient.
- Less intuitive than a direct comparison-based approach.
Way 3: Best
To avoid slicing altogether, we can use indexes to track where we are in the list — this way, we reuse the same list and avoid extra memory usage.
def find_max(lst, idx=0):
if idx == len(lst) - 1:
return lst[idx]
max_rest = find_max(lst, idx + 1)
return max(lst[idx], max_rest)
Example 8: Count digits of a number
def count_digits(n):
n = n//10
if n == 0:
return 1
return 1 + count_digits(n) if n > 0 else 0Example 9: Power of a number (e.g., 2^n)
def power_two(n):
if n ==1:
return 1
return 2*power_two(n-1) Any Base
def power(base, exponent):
if exponent == 0:
return 1
return base * power(base, exponent - 1)Example 10: Fibonacci series (nth term)
f(0) => 0
f(1) => 1
f(2) => f(1) + f(0)
f(3) => f(2) + f(3)
f(4) => f(3) + f(2)
f(5) => f(4) + f(3)
def fibonacci(n):
if n == 0:
return 0
if n == 1:
return 1
return fibonacci(n-1)+fibonacci(n-2)- The basic recursive version is very slow for large n because it recalculates the same values many times.
- Instead of calculation again and again same. What if we can Memoization the results and use that.
- Will see that in Dynamic Programming
Example 11: Sum of elements in a list
Way 1
def sum_list(lst):
if len(lst)==0:
return 0
return lst[0]+sum_list(lst[1:])Using lst[1:] creates a new list at each recursive call, which is fine for small lists, but not optimal for large ones due to extra memory usage.
Way 2:
def sum_list(lst, idx=0):
if idx == len(lst):
return 0
return lst[idx] + sum_list(lst, idx + 1)
Coming Soon
Intermediate Level
- Binary search (recursive version)
- Count occurrences of an element in a list
- Product of list elements
- Find GCD (Greatest Common Divisor) using recursion
- Check if array is sorted
- Convert decimal to binary
- Replace all occurrences of a character in a string
Advanced Level
- Generate all subsets (power set) of a set
- Tower of Hanoi
- N-th catalan number
- .
- Maze solver (backtracking)
- N-Queens problem
- Recursive tree/graph traversal (DFS)
- Sudoku solver (backtracking)
- Word break problem
- Subset sum problem
Example 22: Generate all permutations of a string or list
def permute(lst):
if len(lst) == 1:
return [lst]
result = []
for i in range(len(lst)):
current = lst[i]
remaining = lst[:i] + lst[i+1:]
for p in permute(remaining):
result.append([current] + p)
return result
permutations = permute([1, 2, 3, 4])
for p in permutations:
print(p)
'''
Output
[1, 2, 3, 4]
[1, 2, 4, 3]
[1, 3, 2, 4]
....
....
'''Permutaion with duplicaton
Way 1:
def permute_unique(lst):
if len(lst) == 1:
return [lst]
result = set()
for i in range(len(lst)):
current = lst[i]
remaining = lst[:i] + lst[i+1:]
for p in permute_unique(remaining):
result.add(tuple([current] + p)) # tuple to store in set
return [list(p) for p in result]Instead of result as list, we can use set
Why not just add the list directly?
result.add(tuple([current] + p))Because lists are mutable and cannot be added to a set.
set.add([1, 2, 3]) # ❌ TypeError: unhashable type: 'list'But tuples are immutable and can be added to a set:
set.add((1, 2, 3)) # ✅ Works fineConvert back to list
return [list(p) for p in result]Way 2 :
def permute_unique(lst):
if len(lst) == 0:
return [[]]
lst.sort()
result = []
prev = None
for i in range(len(lst)):
if lst[i] == prev:
continue # Skip duplicates
rest = lst[:i] + lst[i+1:]
for p in permute_unique(rest):
result.append([lst[i]] + p)
prev = lst[i]
return result
How it works:
- lst.sort() puts duplicate elements next to each other.
- prev tracks the last value used at this level.
- If we see the same value again, we skip it to avoid generating the same permutation.
Instead of all these, we can also use backtracking.
Backtracking
Backtracking is a problem-solving technique where you explore different options to find a solution, and if a path leads to a dead end, you “backtrack” to a previous point and try a different path.
What is backtracking?
Backtracking is a method of exploring all possible options to solve a problem, and “backtracks” (undoes the last step) when a path doesn’t lead to a solution.
Backtracking is a general algorithmic technique that:
- Explores all possible decisions (choices),
- Proceeds recursively,
- Undoes previous decisions (backtracks) to explore other possibilities.
Think of it like:
- Trying all the keys on a keyring to open a lock.
- If a key doesn’t work, you go back and try the next one.
Basic form of backtracking
def explore(index, path):
if index == len(nums): # Base case: all decisions made
print(path)
return
# Choose to include nums[index]
explore(index + 1, path + [nums[index]])
# Choose to exclude nums[index]
explore(index + 1, path)
nums = ['a','b','c']
explore(0,[])
'''
Output
['a', 'b', 'c']
['a', 'b']
['a', 'c']
['a']
['b', 'c']
['b']
['c']
[]
'''- At each step, you make a decision: include or exclude the current element.
- Include explore(index + 1, path + [nums[index]])
- exclude explore(index + 1, path)
- Include nums[index] → left branch
- Exclude nums[index] → right branch
- Like include a , exclude a etc
- You recursively explore both branches.
- path + […] creates a new path, so the current call doesn’t need to undo changes (because Python lists are immutable in this context).
- Stopping criteria : index == len(nums), when decision tree reached end
Level 0 (start)
[]
/ \
a -
/ \ / \
ab a b -
/ \ / \ / \ / \
abc ab ac a bc b c -it’s a clean, minimal example — perfect for understanding the concept of decision trees and subset generation
But it avoids the more complex features often associated with full-fledged backtracking problems:
- No state mutation to undo
- You’re building a new path each time using path + […], so there’s no need to explicitly backtrack (i.e., remove the last choice).
- In more involved backtracking problems (like permutations, Sudoku, N-Queens), you typically mutate shared state and then undo that mutation after recursion:
path.append(nums[i])
backtrack(...)
path.pop() # backtracking step- No constraints or pruning
- Advanced backtracking often includes constraints (e.g., only valid Sudoku numbers, safe positions in N-Queens).
- It may also involve pruning the search space early (i.e., “forward checking”).
- Small and fixed decision tree
- Each index has exactly two choices (include or exclude), and there’s no backjumping, heuristics, or dynamic branching.
Then show me the real
Real Backtracking
def backtrack(index, path):
if index == len(nums):
print(path[:]) # print a copy of the current path
return
# Choose to include nums[index]
path.append(nums[index]) # mutate
backtrack(index + 1, path) # explore
path.pop() # undo (backtrack)
# Choose to exclude nums[index]
backtrack(index + 1, path) # no change to path
nums = ['a', 'b', 'c']
backtrack(0, [])Basic Code
explore(index + 1, path + [nums[index]])
explore(index + 1, path)Every time we have different path
if index == len(nums): # Base case: all decisions made
print(path ,id(path))
return
'''
['a', 'b', 'c'] 4364734976
['a', 'b'] 4365063744
['a', 'c'] 4364734976
['a'] 4365070656
['b', 'c'] 4365063744
['b'] 4364734976
['c'] 4365063744
[] 4364339520
''' Here’s what it does:
- path + [nums[index]] creates a brand new list every time.
- So there’s no need to undo anything, because:
- Every recursive call works with its own copy of the path.
The old path is untouched.
✅ It works and is clean — but it doesn’t show what backtracking truly is.
Real Code
path.append(nums[index])
backtrack(index + 1, path)
path.pop()Here’s what changed:
- path is now a shared list
- We use append() to add an element.
- This modifies the same list (path) in memory — no new list is made.
- After exploring a choice, we must undo it
- That’s what path.pop() does — it removes the last added element, bringing the list back to its previous state.
if index == len(nums):
print(path[:],id(path[:])) # print a copy of the current path
return
'''
['a', 'b', 'c'] 4300244096
['a', 'b'] 4300248384
['a', 'c'] 4300248384
['a'] 4300248384
['b', 'c'] 4300248384
['b'] 4300248384
['c'] 4300248384
[] 4300248384
''' | Step | Your Code | Real Backtracking Code |
|---|---|---|
| Add an element | path + [x] → new list | path.append(x) → modify same list |
| Recurse | on a new path | on the same path |
| Go back (return) | nothing to undo | must path.pop() to undo |
Why This Matters?
In simple problems like subset generation, both versions work.
But in harder problems (e.g., permutations, Sudoku, N-Queens):
- You can’t keep copying the entire state every time.
- You must reuse and undo, i.e., mutate + backtrack.
Backtracking = make a decision → explore → undo decision → try next oneFinal Code: Returing the result
def backtrack(index, path, result):
if index == len(nums):
result.append(path[:]) # append a copy of the current path
return
# Include nums[index]
path.append(nums[index])
backtrack(index + 1, path, result)
path.pop()
# Exclude nums[index]
backtrack(index + 1, path, result)
# Example usage
nums = ['a', 'b', 'c']
result = []
backtrack(0, [], result)
print(result)
'''
[['a', 'b', 'c'], ['a', 'b'], ['a', 'c'], ['a'], ['b', 'c'], ['b'], ['c'], []]
'''Why path[:] not path?
- Use print(path[:]) if you want to print a copy of the current state of the path at that moment.
- Use print(path) and you’ll be printing the same list object, which might get mutated later due to backtracking — potentially leading to unexpected output if you’re storing the results.
if index == len(nums):
result.append(path) # append a copy of the current path
return
'''
[[], [], [], [], [], [], [], []] # last value of path get reflected in all
''' print(path)
This prints a reference to the same list object used throughout recursion. If the list is changed later (which it is, due to path.pop()), then any saved reference will reflect the updated content.
print(path[:])
This creates a shallow copy of the list at that moment, which is safe from future mutations. It’s important when:
- You’re storing paths (e.g., in a result list).
- You want to see the snapshot of the path at the time of recursion.
When we use print at same point, we have correct result, but later path get change.
- last value of path is [], which get reflected in all places.
if index == len(nums):
print(path) # append a copy of the current path
return
'''
['a', 'b', 'c']
['a', 'b']
['a', 'c']
['a']
['b', 'c']
['b']
['c']
[]
''' path[:] and path[::]
- These two are functionally identical in the context of making a shallow copy of a list.
- Both can we use interchangeably
why is path[:] more common?
- Readability: [:] is more idiomatic and widely recognized as “copy the list.”
- Simplicity: [:] avoids the extra : which may make people think of slicing with a step (path[::2], etc.).
- Convention: Python community tends to use [:] for shallow copies unless the step matters.
Use :: for slicing and : for shallow copy
Back to basic
Permutations
- All possible arrangements of the elements
- Order Matters
- Total permutations = factorial of (element)
Combinations
- All possible selections of elements
- Order Doesn’t Matter, Example abc , bca, cba etc all are same
C(n,k)= k!(n−k)!/ n- n = total number of elements in the set
- k = number of elements you want to choose from that set
Example : a, b, c
Permutations
[a, b, c]
[a, c, b]
[b, a, c]
[b, c, a]
[c, a, b]
[c, b, a]Combinations
1-element combinations:
[a]
[b]
[c]
2-element combinations:
[a, b]
[a, c]
[b, c]
3-element combinations:
[a, b, c]Practice
Example 1 : Subset Generation (Combinations)
Variation 1:
def backtrack(index, path, result):
if index == len(nums):
result.append(path[:]) # append a copy of the current path
return
# Include nums[index]
path.append(nums[index])
backtrack(index + 1, path, result)
path.pop()
# Exclude nums[index]
backtrack(index + 1, path, result)
# Example usage
nums = ['a', 'b', 'c']
result = []
backtrack(0, [], result)
print(result)
'''
[['a', 'b', 'c'], ['a', 'b'], ['a', 'c'], ['a'], ['b', 'c'], ['b'], ['c'], []]
'''Decision Tree
Level 0 (start)
[]
/ \
a -
/ \ / \
ab a b -
/ \ / \ / \ / \
abc ab ac a bc b c -Variation 2:
def backtrack(index, path):
result.append(path[:])
for i in range(index, len(nums)):
path.append(nums[i])
backtrack(i + 1, path)
path.pop()
result = []
nums = ['a','b','c']
backtrack(0,[])
print(result)
'''
[[], ['a'], ['a', 'b'], ['a', 'b', 'c'], ['a', 'c'], ['b'], ['b', 'c'], ['c']]
'''Logics
Why no return is needed?
We use i + 1 in the recursive call to ensure that each recursive step moves forward through the list. Because of this forward-only movement, the recursion naturally reaches the end of the list without needing an explicit return
Why i+1 is used?
When generating subsets, we are not interested in all possible orderings of elements (like [‘a’, ‘b’] and [‘b’, ‘a’]), because in a subset, order doesn’t matter. So [‘a’, ‘b’] and [‘b’, ‘a’] are considered the same subset.
To avoid generating such duplicate permutations, we make sure that in every recursive step, we only look at elements that come after the current one. That’s why we use i + 1 in the recursive call
Decision Tree
[]
___________|___________
| | |
['a'] ['b'] ['c']
| | |
____|____ ___|___ |
| | | | |
['a','b'] ['a','c'] ['b','c'] (backtrack)
| | |
['a','b','c'] (backtrack) (backtrack)
|
(backtrack)Example 2: Permutations
Variation 1:
def permute(lst):
if len(lst) ==1:
return [lst]
result = []
for i in range(len(lst)):
current = lst[i]
remaining = lst[:i]+lst[i+1:]
for p in permute(remaining):
result.append([current]+p)
return result
lst=['a','b','c']
result = permute(lst)
print(result)
'''
[['a', 'b', 'c'], ['a', 'c', 'b'], ['b', 'a', 'c'], ['b', 'c', 'a'], ['c', 'a', 'b'], ['c', 'b', 'a']]
'''Variation 2
def backtrack(path, used):
if len(path) == len(nums):
print(path[:]) # copy to avoid mutation issues
return
for i in range(len(nums)):
if used[i]:
continue # skip already used elements
# Choose
path.append(nums[i])
used[i] = True
# Explore
backtrack(path, used)
# Backtrack
path.pop()
used[i] = False
nums = ['a', 'b', 'c']
backtrack([], [False] * len(nums))
'''
['a', 'b', 'c']
['a', 'c', 'b']
['b', 'a', 'c']
['b', 'c', 'a']
['c', 'a', 'b']
['c', 'b', 'a']
'''Logic
Loop is always from 0 to length
In permutations, order matters. So you must try placing every available element at every position, which requires looping from 0 to len(nums) at each recursion level.
Return is required
The return is needed once the path is complete. Without it, the function would continue even after a complete permutation is formed, which isn’t necessary and might mess with logic.
Then even after you find a full permutation, like [‘a’, ‘b’, ‘c’], the function continues running — it goes on to the for loop below and tries to add more elements, even though the path is already complete.
Why used is required?
Without used, the same index (e.g. the ‘a’ at index 0) could be used multiple times in one permutation. That would give invalid permutations like ‘aaa’ or duplicates like ‘aba’ appearing multiple times.
Decision Tree
[]
___________|___________
| | |
a b c
__|__ __|__ __|__
| | | | | |
ab ac ba bc ca cb
| | | | | |
abc acb bac bca cab cba
Logic comparison : Subset vs Permutations
backtrack(i+1)
- As order doen’t matter(abc=bca etc)
- when choosing the next element, we move forward to the next index (i + 1), ensuring we never revisit previous elements.
'''
[[], ['a'], ['a', 'b'], ['a', 'b', 'c'], ['a', 'c'], ['b'], ['b', 'c'], ['c']]
'''- See the output ‘a’ is used in the first position, then we move one to b then c
- all combination a, then b, then c
- i + 1 restricts the search space to forward-only elements.
if used[i]:
- This is used to skip elements that are already in the current permutation path.
- It’s about avoiding duplicates in the path, not about limiting index range.
- The loop still checks every index from 0 to n – 1 on every level of recursion.
Example 3: Combination with duplicates
def backtrack(index, path):
result.append(path[:])
for i in range(index, len(nums)):
# Skip duplicates: only use the *first* in loop
if i > index and nums[i] == nums[i - 1]:
continue
path.append(nums[i])
backtrack(i + 1, path)
path.pop()
result = []
nums = ['a', 'b', 'a']
nums.sort()
backtrack(0, [])
print(result)
'''
[[], ['a'], ['a', 'a'], ['a', 'a', 'b'], ['a', 'b'], ['b']]
'''Logic
- nums[i] == nums[i – 1]: we’ve already considered this number in this position, so skip to avoid duplicates.
- i > index: means this is not the first number we’re checking in this loop.
Example a,a
we should consider first a , and avoid later a
Purpose of i > index
- Ensures that duplicates are only skipped within the same recursive call level.
- If we’re at a new recursive level (deeper in the tree), we want to allow the duplicate again if it’s chosen as part of a different path.
Example 4: Permutations with Duplicates
def backtrack(path, used):
if len(path) == len(nums):
result.append(path[:])
return
for i in range(len(nums)):
if used[i]:
continue
# Skip duplicates: only use the *first* occurrence
if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
continue
used[i] = True
path.append(nums[i])
backtrack(path, used)
path.pop()
used[i] = False
nums = [1, 1, 2]
nums.sort()
result = []
backtrack([], [False]*len(nums))
print(result) #[[1, 1, 2], [1, 2, 1], [2, 1, 1]]
i > 0
This ensures we are not checking outside the array bounds when accessing nums[i – 1].
nums[i] == nums[i – 1]:
This checks if the current number is the same as the previous number. If true, we might be in a situation where a duplicate permutation could be formed.
not used[i – 1]
- This checks whether the previous identical element was already used in the current recursive path.
- If it’s not used, it means we’re still in the same recursive depth level (i.e., trying options for the same decision).
- On the other hand, if used[i – 1] is True, it means we included the previous duplicate in the current path — so it’s safe to include the current one as well, potentially forming a new unique permutation.
Without this check, your solution would generate duplicate permutations like [1,1,2] more than once.
✅ In short: It’s a way to prevent generating duplicate permutations by ensuring we only use the first occurrence of a duplicate number in any given recursive level.
Example 5: Combination
Given two integers n and k, return all possible combinations of k numbers chosen from the range [1, n].
You may return the answer in any order.
def backtrack(start, path):
if len(path) == k:
result.append(path[:])
return
for i in range(start, n + 1):
path.append(i) # Choose
backtrack(i + 1, path) # Explore (i+1 → no reuse)
path.pop() # Un-choose
n = 4
k = 2
result = []
backtrack(1, [])
print(result)
'''
Input: n = 4, k = 2
Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
'''Example 6: Combination Sum
Given an array of positive integers candidates (no duplicates) and a target integer target, return all unique combinations of candidates where the chosen numbers sum to target.
You may use the same number unlimited times.
def backtrack(index, path):
if sum(path) == target:
result.append(path[:])
return
if sum(path) > target:
return
for i in range(index, len(candidates)):
path.append(candidates[i]) # Choose
backtrack(i, path) # Explore (reuse allowed)
path.pop() # Un-choose
candidates = [2, 3, 6, 7]
target = 7
result = []
backtrack(0, [])
print(result)
'''
[[2, 2, 3], [7]]
'''backtrack(i, path)
- i not i+1, because repetition of a digit is allowed
Example 7: Combination Sum II – (No Reuse, With Duplicates)
Given a collection of candidate numbers candidates (can include duplicates) and a target number target, find all unique combinations where the chosen numbers sum to the target.
Each number may only be used once.
The solution set must not contain duplicate combinations.
def explore(index,path):
if sum(path)==target:
result.append(path[:])
if sum(path)>target:
return
for i in range(index,len(nums)):
if i>index and nums[i]==nums[i-1]:
continue
path.append(nums[i])
explore(i+1,path)
path.pop()
result = []
nums = [10,1,2,7,6,1,5]
target = 8
nums.sort()
explore(0,[])
print(result)
'''
[[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]]
'''