9.9
Back-tracking scheme
1. Sort the multiset once (so equal numbers are consecutive).
2. Process the numbers left-to-right; for the i-th distinct value v occurring c times you may pick it 0…c times, provided the running sum never exceeds t.
3. Whenever the remaining total becomes 0 the current multiset of picks is a valid solution; store a copy.
4. Because each element is handled only from its first appearance onward, every combination is produced in non-decreasing order ⇒ no duplicates.
def subset_sum(multiset, t):
multiset.sort()
# compress into (value, multiplicity)
nums = []
for v in multiset:
if not nums or nums[-1][0] != v:
nums.append([v, 1])
else:
nums[-1][1] += 1
out, cur = [], []
def dfs(idx, remaining):
if remaining == 0:
out.append(cur.copy())
return
if idx == len(nums) or remaining < 0:
return
val, cnt = nums[idx]
# try picking the value 0..cnt times
for k in range(cnt + 1):
if k * val > remaining:
break
cur.extend([val] * k)
dfs(idx + 1, remaining - k * val)
del cur[-k:] # back-track
dfs(0, t)
return out
Example
t = 4, S = [4,3,2,2,1,1] produces:[[4], [3,1], [2,2], [2,1,1]]Complexity
Let M be the number of valid subsets. Time: O(M + 2n) in the worst case (every subset explored), but far smaller in practice because branches that overshoot t are pruned early. Space: O(n) for the recursion stack plus O(M · n) to store the results.
Back to
Chapter 9
