给定一个整数数组和一个目标值,找到所有相加等于该目标值的下标,比如arr{3,5,2,6},目标值是11,则返回1,3和0,2,3
时间: 2023-06-19 16:09:55 浏览: 88
数组中数值和下标相等的元素.md
可以使用回溯算法来解决这个问题。首先对数组进行排序,从小到大逐个枚举数组中的数,对于每个数,可以选择将其加入当前的组合中,或者不加入。如果加入当前的组合中,继续递归处理下一个数,直到找到一个组合的和等于目标值,将其加入结果列表中。如果不加入当前的组合中,直接递归处理下一个数。
以下是使用 Python 实现的代码:
```python
def combination_sum(nums, target):
nums.sort()
res = []
def backtrack(start, target, path):
if target == 0:
res.append(path)
return
for i in range(start, len(nums)):
if nums[i] > target:
break
backtrack(i, target - nums[i], path + [i])
backtrack(0, target, [])
return res
# 示例
nums = [3, 5, 2, 6]
target = 11
print(combination_sum(nums, target)) # 输出 [[0, 2, 3], [1, 3]]
```
其中,backtrack 函数中的 start 参数表示从数组中的哪个位置开始枚举,path 参数记录当前的组合。在每次递归中,如果找到一个组合的和等于目标值,则将其加入结果列表中。最后返回结果列表即可。
阅读全文