文章目录
子集II
思路分析：求解子集的问题的关键就是，通过递归与回溯，我们就是得确定以某个元素开始的子集，对于这个题目来说，比较麻烦的一点就是，存在重复的元素，这样如果不增加一个判断的话，会导致我们的结果存在重复的元素
如何消除重复的情况？
nums.sort() # 排序，方便去重
# 在这个for 训练里面，我们是用于选择子集的开始的元素的，只要我们开始的元素没有和前一个元素相同，那么就可以进行递归增加元素
if i > start and nums[i] == nums[i-1]:
continue
整体的代码中，我们使用ans 来记录全部的子集，path来记录当前的元素的情况
class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
nums.sort() # 排序，方便去重
ans = []
path = []
def backtrack(start):
ans.append(path[:]) # 添加当前子集到结果中
for i in range(start, len(nums)):
# 跳过重复元素
if i > start and nums[i] == nums[i-1]:
continue
path.append(nums[i]) # 选择当前元素
backtrack(i + 1) # 递归
path.pop() # 撤销选择
backtrack(0)
return ans
1191.K次串联后最大子数组之和
思路分析：由于k和arr数组长度都很长，所以不可能全部拼接起来，所以说就根本不用全部拼接起来
规律：当k=1的时候，就是正常算，如果K>=2的时候，我们可以先拼接两个进行正常运算，如果max(dp) 小于等于0，则返回0，然后我们思考这两段之间能否插入剩余的段，所以我们计算sum(arr),如果sum(arr)>0,就可以拼接在两段之间，否则就直接返回两段的情况，记得要取模再返回
class Solution:
def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
# 肯定是不能直接拼接上去再dp的不然，o(n)的时间复杂度也到了10^10,所以还是在之前的数组arr操作
#
n = len(arr)
ans = 0
if k == 1:
dp = [0]*n
dp[0] = arr[0]
for i in range(1,n):
dp[i] = max(dp[i-1]+arr[i],arr[i])
# 判断ans,如果小于等于0，就返回0，否则就是取模返回
ans = max(dp)
return ans%(10**9+7) if ans >0 else 0
else:
dp = [0]*(2*n)
dp[0] = arr[0]
# 拼接
nums = arr + arr
for i in range(1,2*n):
dp[i] = max(dp[i-1]+nums[i],nums[i])
# 查看最大值
ans = max(dp)
# 小于等于0就返回
if ans<=0:
return 0
sumarr = sum(arr)
# 看看能否插入其中
if sumarr>0:
return (ans+(k-2)*sumarr)%(10**9+7)
else:
return ans%(10**9+7)