楠君的小窝

解题思路 代码 Python 123456789101112131415161718192021222324252627282930313233class Solution: def solveSudoku(self, board: List[List[str]]) -> None: def dfs(pos: int): nonlocal valid if pos == len(spaces): valid = True return i, j = spaces[pos] for digit in range(9): if line[i][digit] == column[j][digit] == block[i // 3][j // 3][digit] == False: line[i][digit] = column[j ...

解题思路 题目要求子序列至少2个元素且递增，那么我们添加条件可以是当path中有两个元素的时候 使用哈希表记录当前层使用过的元素，若再次碰到直接continue 当nums[i] < path的最后一个元素时则continue 代码 Python 12345678910111213141516171819class Solution: def findSubsequences(self, nums: List[int]) -> List[List[int]]: result = [] def backtracking(startIndex: int, path: list[int]) -> None: if len(path) >= 2: result.append(path.copy()) uset = set() for i in range(startIndex, len(nums)): ...

解题思路 将nums数组所有子集添加进去就行 代码 Python 1234567891011121314class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: result = [[]] def dfs(startIndex: int, temp: list[int]): if startIndex == len(nums): return for i in range(startIndex, len(nums)): temp.append(nums[i]) result.append(temp.copy()) dfs(i + 1, temp) temp.pop() dfs(0, []) return result C++ 12345 ...

解题思路 首先需要一个check函数用来验证字符串是否为回文串，这里check我们选用双指针。 从下标0开始不断查找回文串，当下标到达s长度时添加进result 代码 Python 1234567891011121314151617181920212223242526class Solution: def partition(self, s: str) -> List[List[str]]: result = [] def check(s: str): l, r = 0, len(s) - 1 while l <= r: if s[l] != s[r]: return False l += 1 r -= 1 return True def backtracking(temp: list[str], start: int): if start == le ...

解题思路 这题就是排序直接使用回溯，考点可能就是几个剪枝的地方。 当总和 > target时 代码 Python 1234567891011121314151617class Solution: def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: answer = [] def backtracking(start: int, temp: list[int], s: int): if s == target: answer.append(temp.copy()) return for i in range(start, len(candidates)): if s + candidates[i] > target: return temp.append(cand ...

解题思路 这题大概的代码与全排列(LC46)差不多,它们的区别是给定的nums中包含重复的元素，那么我们在遍历的时候要记录当前这层是否已经使用过某个元素了，如果已经使用过了则跳过。同样使用的是哈希表，不过这次记录的不是下标而是元素值。 代码 Python 123class Solution: def permuteUnique(self, nums: List[int]) -> List[List[int]]: return list(set(permutations(nums))) C++ 123456789101112131415161718192021222324252627282930class Solution { vector<int> vis;public: void backtrack(vector<int>& nums, vector<vector<int>>& ans, int idx, vector<int>& perm) { ...