在数组中找任意个数的数字,满足他们的和是给定数字
时间: 2024-05-15 08:18:28 浏览: 15
这是一个经典的问题,可以使用递归的方式解决。具体方法是:首先将数组排序,然后从小到大依次枚举数组中的每一个数字,如果当前数字等于给定的数字,那么直接返回;否则,递归搜索剩余的数字,直到找到了符合条件的数字或者所有数字都搜索完毕。如果找到了符合条件的数字,就返回true,否则返回false。
以下是基于Python的代码实现:
```python
def find_nums_with_sum(nums, target_sum):
nums.sort()
return find_with_sum(nums, target_sum, 0)
def find_with_sum(nums, target_sum, start):
if target_sum == 0:
return True
n = len(nums)
for i in range(start, n):
if nums[i] > target_sum:
return False
if i > start and nums[i] == nums[i-1]:
continue
if find_with_sum(nums, target_sum-nums[i], i+1):
return True
return False
```
使用示例:
```python
nums = [1, 2, 5, 7, 9, 12, 17]
target_sum = 14
result = find_nums_with_sum(nums, target_sum)
print(result) # True
```
注意:由于题目要求可以任意选取数字,因此代码中使用了递归的方式进行搜索,可能存在效率比较低的问题。如果需要优化效率,可以使用动态规划等算法进行改进。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)