General Backtracking questions solutions in Python for reference :
I have taken solutions of @caikehe from frequently asked backtracking questions which I found really helpful and had copied for my reference. I thought this pos
I have taken solutions of @caikehe from frequently asked backtracking questions which I found really helpful and had copied for my reference. I thought this post will be helpful for everybody as in an interview I think these basic solutions can come in handy. Please add any more questions in comments that you think might be important and I can add it in the post.\n\n#### Combinations :\n```\ndef combine(self, n, k):\n    res = []\n    self.dfs(xrange(1,n+1), k, 0, [], res)\n    return res\n    \ndef dfs(self, nums, k, index, path, res):\n    #if k < 0:  #backtracking\n        #return \n    if k == 0:\n        res.append(path)\n        return # backtracking \n    for i in xrange(index, len(nums)):\n        self.dfs(nums, k-1, i+1, path+[nums[i]], res)\n```  \n\t\n#### Permutations I\n```\nclass Solution:\n    def permute(self, nums: List[int]) -> List[List[int]]:\n        res = []\n        self.dfs(nums, [], res)\n        return res\n\n    def dfs(self, nums, path, res):\n        if not nums:\n            res.append(path)\n            #return # backtracking\n        for i in range(len(nums)):\n            self.dfs(nums[:i]+nums[i+1:], path+[nums[i]], res)\n```        \n\n#### Permutations II\n```\ndef permuteUnique(self, nums):\n    res, visited = [], [False]*len(nums)\n    nums.sort()\n    self.dfs(nums, visited, [], res)\n    return res\n    \ndef dfs(self, nums, visited, path, res):\n    if len(nums) == len(path):\n        res.append(path)\n        return \n    for i in xrange(len(nums)):\n        if not visited[i]: \n            if i>0 and not visited[i-1] and nums[i] == nums[i-1]:  # here should pay attention\n                continue\n            visited[i] = True\n            self.dfs(nums, visited, path+[nums[i]], res)\n            visited[i] = False\n```\n\n \n#### Subsets 1\n\n\n```\ndef subsets1(self, nums):\n    res = []\n    self.dfs(sorted(nums), 0, [], res)\n    return res\n    \ndef dfs(self, nums, index, path, res):\n    res.append(path)\n    for i in xrange(index, len(nums)):\n        self.dfs(nums, i+1, path+[nums[i]], res)\n```\n\n\n#### Subsets II  \n\n\n```\ndef subsetsWithDup(self, nums):\n    res = []\n    nums.sort()\n    self.dfs(nums, 0, [], res)\n    return res\n    \ndef dfs(self, nums, index, path, res):\n    res.append(path)\n    for i in xrange(index, len(nums)):\n        if i > index and nums[i] == nums[i-1]:\n            continue\n        self.dfs(nums, i+1, path+[nums[i]], res)\n```\n\n\n#### Combination Sum        \n\n\n```\ndef combinationSum(self, candidates, target):\n    res = []\n    candidates.sort()\n    self.dfs(candidates, target, 0, [], res)\n    return res\n    \ndef dfs(self, nums, target, index, path, res):\n    if target < 0:\n        return  # backtracking\n    if target == 0:\n        res.append(path)\n        return \n    for i in xrange(index, len(nums)):\n        self.dfs(nums, target-nums[i], i, path+[nums[i]], res)\n```\n\n        \n        \n#### Combination Sum II        \n\n```\ndef combinationSum2(self, candidates, target):\n    res = []\n    candidates.sort()\n    self.dfs(candidates, target, 0, [], res)\n    return res\n    \ndef dfs(self, candidates, target, index, path, res):\n    if target < 0:\n        return  # backtracking\n    if target == 0:\n        res.append(path)\n        return  # backtracking \n    for i in xrange(index, len(candidates)):\n        if i > index and candidates[i] == candidates[i-1]:\n            continue\n        self.dfs(candidates, target-candidates[i], i+1, path+[candidates[i]], res)\n```
['Backtracking', 'Python', 'Python3']