求个算法, 组合总和类型的, 从给定数组中取数, 要求取出来的数字总和在某个范围内

[bthulu]

1. 给定数字数组 candidates, 和一个目标范围 [min, max] ，找出 candidates 中所有可以使数字和 >=min 且<=max 的组合。

例如: 输入: candidates = [10, 20, 20, 30, 40], [min, max] = [30, 50] 输出: [[10, 20], [10, 30], [10, 40], [10, 20, 20], [20, 20], [20, 30], [30], [40]]

1. 给定数字数组 candidates, 和一个目标数 target ，另一个小于 target 的目标数 target1 , 找出 candidates 中所有可以使数字和 > target , 且拿掉任一一个数字后的数字和 < target , 且拿掉某一个数字后的数字和 <= target - target1 的组合。

例如: 输入: candidates = [10, 20, 20, 30], target = 45, target1 = 10 输出: [[20, 30], [10, 20, 20]]

以上都是我这边现实业务需要计算的场景, 我根据 leetcode 上的组合总和 II改了改算是勉强将第一个算法实现了

第二个算法实在是不会搞了

[kamilic]

不是很懂算法，但以前有了解过一些 leetcode 解法。
我觉得先考虑先粗暴做出来，再进行性能优化？
先从 candidates 中找出字和 > target 的输出 A ，再从 A 中找 < target 的输出 B ， 再从 B 中找 <= target - target1 的组合 C 。

优化方向的话，在查找组合和的过程中，应该有很多运算结果可以复用的。

[yao177]

为了解决这个问题，我们可以采用回溯的方法来找到所有符合条件的组合。具体步骤如下：

1. **排序**：首先对数组 `candidates` 进行排序，这有助于优化搜索过程并减少重复。
2. **回溯**：通过递归函数遍历所有可能的组合，并在每个步骤中进行条件检查。
3. **条件检查**：
- 确保当前组合的和大于 `target`。
- 对于当前组合中的每个元素，移除该元素后的和应小于 `target`。
- 对于当前组合中的每个元素，移除该元素后的和应小于或等于 `target - target1`。

下面是一个 Python 实现的例子：

```python
def find_combinations(candidates, target, target1):
candidates.sort() # 排序以优化搜索
results = []

def backtrack(comb, start, current_sum):
# 检查当前组合是否满足条件
if current_sum > target:
# 检查移除任意一个元素后是否满足所有条件
all_valid = True
for i in range(len(comb)):
new_sum = current_sum - comb[i]
if new_sum < target and new_sum <= target - target1:
continue
else:
all_valid = False
break

if all_valid:
results.append(comb.copy())
return

# 继续添加元素到组合中
for i in range(start, len(candidates)):
# 为了避免重复组合，跳过相同的元素
if i > start and candidates[i] == candidates[i - 1]:
continue
comb.append(candidates[i])
backtrack(comb, i + 1, current_sum + candidates[i])
comb.pop() # 回溯

backtrack([], 0, 0)
return results

# 示例输入
candidates = [10, 20, 20, 30]
target = 45
target1 = 10
# 函数调用
output = find_combinations(candidates, target, target1)
print(output)
```

这个代码首先定义了一个回溯函数 `backtrack`，该函数尝试在 `candidates` 中找到所有符合条件的组合。我们使用 `comb` 来存储当前的组合，使用 `current_sum` 来跟踪当前组合的总和。如果当前组合满足所有条件，我们将其添加到结果列表 `results` 中。我们还使用了一些优化措施，比如跳过重复元素，以减少不必要的计算。

这个算法的时间复杂度较高，对于大数据集可能不够高效，因为它需要检查所有可能的组合。不过，对于小到中等规模的数据集，这个方法应该是可行的。

[dhb233]

这是在算优惠券吗[doge]

[MoYi123]

candidates = [10, 20, 20, 30, 40]
target = 45
target1 = 10

from functools import cache

@cache
def dp(idx, count, min_element, max_element):
if idx == len(candidates):
________if count > target and count - min_element < target and count - max_element <= target - target1:
____________print(count, min_element, max_element)
____________return 1
________return 0
____if not count - min_element < target:
________return 0
____ele = candidates[idx]
____pick = dp(idx + 1, count + ele, min(ele, min_element), max(ele, max_element))
____not_pick = dp(idx + 1, count, min_element, max_element)
____return pick + not_pick


print(dp(0, 0, 4e18, 0))


O(n^3 * target) 只有方案数, 具体方案是什么你自己改一下.

[main1234]

func reverse(arr []int, target1, target2 int) [][]int {
res := make([][]int, 0)
// 先排序
sort.Ints(arr)
// 逆序排序
for i := 0; i < len(arr)/2; i++ {
arr[i], arr[len(arr)-i-1] = arr[len(arr)-i-1], arr[i]
}
sum := 0
track := make([]int, 0)
var fn func(start int)
fn = func(start int) {
if start == len(arr) {
if sum < target1 && sum-track[len(track)-1] < target1 && sum-track[len(track)-1] < target1-target2 {
tmp := make([]int, len(track))
copy(tmp, track)
res = append(res, tmp)
return
}
}
for i := start; i < len(arr); i++ {
sum += arr[i]
track = append(track, arr[i])
fn(i + 1)
track = track[:len(track)-1]
sum -= arr[i]
}
}
fn(0)
return res
}

[main1234]

我的算法应该能继续剪枝

[bthulu]

@main1234 你这个算法有问题啊,
if sum < target1 && sum-track[len(track)-1] < target1 && sum-track[len(track)-1] < target1-target2
是不是应该改成
if sum > target1 ...

[main1234]

@bthulu 对，改成你的判断，然后在 for 里面放两个剪枝就行了

[bthulu]

@main1234 我试了下, 结果不对啊

[lecia]

第一问，01 背包记忆化，最后回溯结果输出。或者递归搜索剪枝也行。
第二问，取第一问结果大于 target 的方案，对每个方案 check ，此方案的每个数字> 方案和-target ，且至少存在一个数字>=方案和-target+target1
第二问递归剪枝感觉能好很多，剪枝条件就是问题中的两个不等式

[main1234]

@bthulu


func reverse(arr []int, target1, target2 int) [][]int {
res := make([][]int, 0)
// 先排序
sort.Ints(arr)
// 逆序排序
for i := 0; i < len(arr)/2; i++ {
arr[i], arr[len(arr)-i-1] = arr[len(arr)-i-1], arr[i]
}
sum := 0
track := make([]int, 0)
var fn func(start int)
fn = func(start int) {
if sum > target1 && sum-track[len(track)-1] < target1 && sum-track[len(track)-1] <= target1-target2 {
tmp := make([]int, len(track))
copy(tmp, track)
res = append(res, tmp)
return
}
for i := start; i < len(arr); i++ {
if sum-arr[i] >= target1 {
continue
}
if sum-arr[i] >= target1-target2 {
continue
}
sum += arr[i]
track = append(track, arr[i])
fn(i + 1)
track = track[:len(track)-1]
sum -= arr[i]
}
}
fn(0)
return res
}

[Sawyerhou]

不知道理解的对不对，目前赞成 10 楼的思路

算法 1 备选方案中，剔除最大元素小于 sum-target+distance 的

[todd7zhang]

反正都输出所有集合了，直接暴力回溯，只要回溯的时候注意去掉重复的就行

```python
def solution2(arr: list[int], lo:int, hi:int) -> list[list[int]]:
def valid(temp):
return all([
sum(temp) > hi,
all((sum(temp[:_i]) + sum(temp[_i+1:])) < hi for _i in range(len(temp))),
any((sum(temp[:_i]) + sum(temp[_i+1:])) <= hi - lo for _i in range(len(temp))),
])

def backtrack(i:int):
if i >= len(arr):
return

for j in range(i, len(arr)):
if j == i or arr[j] != arr[j-1]:
temp.append(arr[j])
if valid(temp):
res.append(temp[:])
backtrack(j+1)
temp.pop()

temp = []
res = []
arr.sort()
backtrack(0)
return res

# solution2([10, 20, 20, 30], 10, 45) -> [[10, 20, 20], [20, 30]]
```

[todd7zhang]

代码乱了，哈哈。直接看 code 链接呢 https://paste.ofcode.org/iHEThFKxvkXHbhmMjAy4TB

[forty]

不考虑性能，用排列组合，生成所有的组合，符合范围的组合就存入结果。
把判别函数作为参数，这样你需要什么样条件的组合，只需要给不同的判别函数进行调用就行，没什么难的。

[cpstar]

应该是深度优先和递归，一个数字只能用一次，然后先取一个数，判断<t1 ，继续取数，直到 t1<sum<t ，作为成功，然后如果 sum>t 则失败弹栈。

[meilicat]

数据范围呢？