# Backtrack Summary: General Solution for 10 Questions!!!!!!!! Python (Combination Sum, Subsets, Permutation, Palindrome)

If you find it helpful, please vote to let more people see this post. Besides, it would be great if you find other questions could be solved use this general solution. Please make a comment below.

39. Combination Sum
https://leetcode.com/problems/combination-sum/

``````    def combinationSum(self, candidates, target):
def backtrack(tmp, start, end, target):
if target == 0:
ans.append(tmp[:])
elif target > 0:
for i in range(start, end):
tmp.append(candidates[i])
backtrack(tmp, i, end, target - candidates[i])
tmp.pop()
ans = []
candidates.sort(reverse= True)
backtrack([], 0, len(candidates), target)
return ans
``````

40. Combination Sum II
https://leetcode.com/problems/combination-sum-ii/

``````    def combinationSum2(self, candidates, target):
def backtrack(start, end, tmp, target):
if target == 0:
ans.append(tmp[:])
elif target > 0:
for i in range(start, end):
if i > start and candidates[i] == candidates[i-1]:
continue
tmp.append(candidates[i])
backtrack(i+1, end, tmp, target - candidates[i])
tmp.pop()
ans = []
candidates.sort(reverse= True)
backtrack(0, len(candidates), [], target)
return ans
``````

78. Subsets
https://leetcode.com/problems/subsets/

``````    def subsets(self, nums):
def backtrack(start, end, tmp):
ans.append(tmp[:])
for i in range(start, end):
tmp.append(nums[i])
backtrack(i+1, end, tmp)
tmp.pop()
ans = []
backtrack(0, len(nums), [])
return ans
``````

90. Subsets II
https://leetcode.com/problems/subsets-ii/

``````    def subsetsWithDup(self, nums):
def backtrack(start, end, tmp):
ans.append(tmp[:])
for i in range(start, end):
if i > start and nums[i] == nums[i-1]:
continue
tmp.append(nums[i])
backtrack(i+1, end, tmp)
tmp.pop()
ans = []
nums.sort()
backtrack(0, len(nums), [])
return ans
``````

46. Permutations
https://leetcode.com/problems/permutations/

``````    def permute(self, nums):
def backtrack(start, end):
if start == end:
ans.append(nums[:])
for i in range(start, end):
nums[start], nums[i] = nums[i], nums[start]
backtrack(start+1, end)
nums[start], nums[i] = nums[i], nums[start]

ans = []
backtrack(0, len(nums))
return ans
``````

47. Permutations II
https://leetcode.com/problems/permutations-ii/

``````    def permuteUnique(self, nums):
def backtrack(tmp, size):
if len(tmp) == size:
ans.append(tmp[:])
else:
for i in range(size):
if visited[i] or (i > 0 and nums[i-1] == nums[i] and not visited[i-1]):
continue
visited[i] = True
tmp.append(nums[i])
backtrack(tmp, size)
tmp.pop()
visited[i] = False
ans = []
visited = [False] * len(nums)
nums.sort()
backtrack([], len(nums))
return ans
``````

60. Permutation Sequence
https://leetcode.com/problems/permutation-sequence/

``````    def getPermutation(self, n, k):
nums = [str(i) for i in range(1, n+1)]
fact = [1] * n
for i in range(1,n):
fact[i] = i*fact[i-1]
k -= 1
ans = []
for i in range(n, 0, -1):
id = k / fact[i-1]
k %= fact[i-1]
ans.append(nums[id])
nums.pop(id)
return ''.join(ans)
``````

131. Palindrome Partitioning
https://leetcode.com/problems/palindrome-partitioning/

``````    def partition(self, s):
def backtrack(start, end, tmp):
if start == end:
ans.append(tmp[:])
for i in range(start, end):
cur = s[start:i+1]
if cur == cur[::-1]:
tmp.append(cur)
backtrack(i+1, end, tmp)
tmp.pop()
ans = []
backtrack(0, len(s), [])
return ans
``````

267. Palindrome Permutation II
https://leetcode.com/problems/palindrome-permutation-ii/
Related to this two:
`31. Next Permutation`: https://leetcode.com/problems/next-permutation/
`266. Palindrome Permutation`: https://leetcode.com/problems/palindrome-permutation/

``````    def generatePalindromes(self, s):
kv = collections.Counter(s)
mid = [k for k, v in kv.iteritems() if v%2]
if len(mid) > 1:
return []
mid = '' if mid == [] else mid[0]
half = ''.join([k * (v/2) for k, v in kv.iteritems()])
half = [c for c in half]

def backtrack(end, tmp):
if len(tmp) == end:
cur = ''.join(tmp)
ans.append(cur + mid + cur[::-1])
else:
for i in range(end):
if visited[i] or (i>0 and half[i] == half[i-1] and not visited[i-1]):
continue
visited[i] = True
tmp.append(half[i])
backtrack(end, tmp)
visited[i] = False
tmp.pop()

ans = []
visited = [False] * len(half)
backtrack(len(half), [])
return ans
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.