[Python3] DFS solutions to 6 different classic backtracking problems & more
I have compiled solutions for all the 6 classic backtracking problems, you can practise them together for better understanding. Good luck with your preparation/
I have compiled solutions for all the 6 classic backtracking problems, you can practise them together for better understanding. Good luck with your preparation/interviews! \n\n[39. Combination Sum](https://leetcode.com/problems/combination-sum/)\n```\nclass Solution:\n    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n        if not candidates: return []\n        res = []\n        candidates.sort()\n        def dfs(idx, path, cur):\n            if cur > target: return\n            if cur == target:\n                res.append(path)\n                return\n            for i in range(idx, len(candidates)):\n                dfs(i, path+[candidates[i]], cur+candidates[i])\n        dfs(0, [], 0)\n        return res\n```\n\n[40. Combination Sum II](https://leetcode.com/problems/combination-sum-ii/discuss/?currentPage=1&orderBy=recent_activity&query=)\n```\nclass Solution:\n    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n        res = []\n        candidates.sort()\n        def dfs(idx, path, cur):\n            if cur > target: return\n            if cur == target:\n                res.append(path)\n                return\n            for i in range(idx, len(candidates)):\n                if i > idx and candidates[i] == candidates[i-1]:\n                    continue\n                dfs(i+1, path+[candidates[i]], cur+candidates[i])\n        dfs(0, [], 0)\n        return res\n```\n[78. Subsets](https://leetcode.com/problems/subsets/)\n```\nclass Solution:\n    def subsets(self, nums: List[int]) -> List[List[int]]:\n        res = []\n        def dfs(idx, path):\n            res.append(path)\n            for i in range(idx, len(nums)):\n                dfs(i+1, path+[nums[i]])\n        dfs(0, [])\n        return res\n```\n\n[90. Subsets II](https://leetcode.com/problems/subsets-ii/)\n```\nclass Solution:\n    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:\n        res = []\n        nums.sort()\n        def dfs(idx, path):\n            res.append(path)\n            for i in range(idx, len(nums)):\n                if i > idx and nums[i] == nums[i-1]:\n                    continue\n                dfs(i+1, path+[nums[i]])\n        dfs(0, [])\n        return res\n```\n\n[46. Permutations](https://leetcode.com/problems/permutations/)\n```\nclass Solution:\n    def permute(self, nums: List[int]) -> List[List[int]]:\n        res = []\n        def dfs(counter, path):\n            if len(path) == len(nums):\n                res.append(path)\n                return\n            for x in counter:\n                if counter[x]:\n                    counter[x] -= 1\n                    dfs(counter, path+[x])\n                    counter[x] += 1\n        dfs(Counter(nums), [])\n        return res \n```\n\n[47. Permutations II](https://leetcode.com/problems/permutations-ii/)\n```\nclass Solution:\n    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n        res = []\n        def dfs(counter, path):\n            if len(path) == len(nums):\n                res.append(path)\n                return\n            for x in counter:\n                if counter[x]:\n                    counter[x] -= 1\n                    dfs(counter, path+[x])\n                    counter[x] += 1\n        dfs(Counter(nums), [])\n        return res\n```\n\nMore good backtracking problems for practice:\n[131. Palindrome Partitioning](https://leetcode.com/problems/palindrome-partitioning/)\n[784. Lettercase Permutation](https://leetcode.com/problems/letter-case-permutation/)\n[1087. Brace Expansion](https://leetcode.com/problems/brace-expansion/)\n[93. Restore IP addresses](https://leetcode.com/problems/restore-ip-addresses/)\n[1079 Letter Tile Possibilities](https://leetcode.com/problems/letter-tile-possibilities/)
['Backtracking', 'Depth-First Search', 'Recursion', 'Python3']