# Backtracking

```class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
subset = []
result = []

#i is index of subset
def dfs(i):
if i >= len(nums):
result.append(subset.copy())
return

#decision to include nums[i]
subset.append(nums[i])
#this recursive call will be given filled subset
dfs(i + 1)

#decision NOT to include nums[i]
subset.pop()
#this recursive call will be given empty subset
dfs(i + 1)

dfs(0)

return result

```
```class Solution:

def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
result = []

#i is index of candidates
def dfs(i, current, total):
if total == target:
#if you do not add .copu() it will append empty arrays
result.append(current.copy())
return
if i >= len(candidates) or total > target:
return

#decision tree has 2 options: 1) add candidates[i] or 2) do not add and move on to next index

current.append(candidates[i])
dfs(i, current, total + candidates[i])
#2) move on to next index
current.pop()
dfs(i + 1, current, total)

dfs(0, [], 0)
return result ```
```class Solution:
#number of permutations = n!
def permute(self, nums: List[int]) -> List[List[int]]:
result = []

if len(nums) == 1:
return [nums[:]]

for i in range(len(nums)):
#pop off first element
n = nums.pop(0)

#numswill now have one less value, will append popped value later
perms = self.permute(nums)

for perm in perms:
perm.append(n)

result.extend(perms)
nums.append(n)

return result
```
```def solution(n, k):
return climb(n, k, [])

def climb(n, k, jumps):
if n == 0:
return [jumps]

out = []

for i in range(1, k+1):
if i > n:
continue

temp = jumps + [i]
out += climb(n-i, k, temp)

return out```
```#solution where you just take subset I and replace last return statement
class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:

subset = []
result = []

#i is index of subset
def dfs(i):
if i >= len(nums):
result.append(subset.copy())
return

#decision to include nums[i]
subset.append(nums[i])
#this recursive call will be given filled subset
dfs(i + 1)

#decision NOT to include nums[i]
subset.pop()
#this recursive call will be given empty subset
dfs(i + 1)

dfs(0)

#need to remove duplicate sublists within result
return ([list(i) for i in {*[tuple(sorted(i)) for i in result]}])

#solution to prevent duplicates in the first place
class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:

result = []
nums.sort()

def backtrack(i, subset):
if i == len(nums):
res.append(subset.copy())
return

#all subsets that include nums[i]
subset.append(nums[i])
backtrack(i + 1, subset)
subset.pop()

#all subsets that don't include nums[i]
while i + 1 < len(nums) and nums[i] == nums[i + 1]:
i += 1
backtrack(i + 1, subset)

backtrack(0, [])

return result

#solution for array with unique integer array. only last return line is dfferent
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
subset = []
result = []

#i is index of subset
def dfs(i):
if i >= len(nums):
result.append(subset.copy())
return

#decision to include nums[i]
subset.append(nums[i])
#this recursive call will be given filled subset
dfs(i + 1)

#decision NOT to include nums[i]
subset.pop()
#this recursive call will be given empty subset
dfs(i + 1)

dfs(0)

return result

```