master
1<<-DOC
2Given a sorted array of integers arr and an integer num, find all possible unique subsets of arr that add up to num.
3Both the array of subsets and the subsets themselves should be sorted in lexicographical order.
4
5Example
6
7For arr = [1, 2, 3, 4, 5] and num = 5, the output should be
8sumSubsets(arr, num) = [[1, 4], [2, 3], [5]].
9
10Input/Output
11
12[time limit] 4000ms (rb)
13[input] array.integer arr
14
15A sorted array of integers.
16
17Guaranteed constraints:
180 ≤ arr.length ≤ 50,
191 ≤ arr[i] ≤ num.
20
21[input] integer num
22
23A non-negative integer.
24
25Guaranteed constraints:
260 ≤ num ≤ 1000.
27
28[output] array.array.integer
29
30A sorted array containing sorted subsets composed of elements from arr that have a sum of num.
31It is guaranteed that there are no more than 1000 subsets in the answer.
32
33 ([1, 2, 3, 4, 5] 5)
34 / \
35 ([2, 3, 4, 5] 4) ([2, 3, 4, 5] 5)
36 / \
37 ([3, 4, 5] 2) ([2, 3, 4, 5] 4)
38 / \
39 ([4, 5] -1) ([3, 4, 5], 2)
40 / \
41 ([4, 5], -1) ([3, 4, 5], 2)
42 / \
43 ([4, 5], -1) ([3, 4, 5], 2)
44DOC
45require 'pp'
46
47describe "sum_subsets" do
48 def sum_subsets(items, target)
49 head = 0
50 tail = items.size - 1
51 results = []
52 found_target = false
53 while head < tail
54 x, y = items[head], items[tail]
55 sum = x + y
56 found_target = true if x == target
57 found_target = true if y == target
58
59 if target == sum
60 if found_target && x > target
61 results << [target]
62 found_target = false
63 end
64 results << [x, y]
65 tail -= 1
66 elsif sum > target
67 tail -= 1
68 elsif sum < target
69 head += 1
70 end
71 end
72 results << [target] if found_target
73 results
74 end
75
76 def sum_subsets(items, target)
77 results = []
78 total = items.sum
79 size = items.size
80
81 return [] if target <= 0
82 return [] if size == 0
83 puts [items, total, target].inspect
84 results.push(items) if total == target
85 return results if size == 1
86
87 first = items[0]
88 1.upto(size - 1) do |n|
89 puts "next"
90 result = sum_subsets(items[n..(size-1)], target - first)
91 results += ([first] + result) if result.any?
92
93 result = sum_subsets(items[n..(size-1)], target)
94 results += (result) if result.size > 0
95 end
96 results
97 end
98
99 def sum_subsets(items, target)
100 i = 0
101 results = []
102 until i >= items.size
103 j = 0
104 until j >= items.size
105 if target == items[i] + items[j]
106 results.push([items[i], items[j]])
107 end
108 if target == items[i] || target == items[j]
109 results.push([target])
110 end
111 j += 1
112 end
113 i += 1
114 end
115 results
116 end
117
118 def sum_subsets(items, target)
119 puts items.inspect
120 matrix = Array.new(items.size) { Array.new(items.size, 0) }
121 (items.size - 1).downto(0) do |i|
122 (items.size - 1).downto(0) do |j|
123 matrix[i][j] = items[i] + items[j]
124 j += 1
125 end
126 i += 1
127 end
128 PP.pp matrix
129
130 []
131 end
132 <<-DOC
133 1, 2, 3, 4, 5
1341 [2, 3, 4, 5, 6]
1352 [3, 4, 5, 6, 7]
1363 [4, 5, 6, 7, 8]
1374 [5, 6, 7, 8, 9]
1385 [6, 7, 8, 9, 10]
139
140 1, 2, 3, 4, 5
1411 [1, 3, 6, 10, 15]
1422 [3, 4, 5, 6, 7]
1433 [4, 5, 6, 7, 8]
1444 [5, 6, 7, 8, 9]
1455 [6, 7, 8, 9, 10]
146 DOC
147
148 # 1, 2, 3, 4, 5
149 def sum_subsets(items, target)
150 last_index = items.size - 1
151 results = []
152 0.upto(last_index) do |i|
153 last_index.downto(i) do |j|
154 subset = items[(i)..j]
155 sum = subset.sum
156 results.push(subset) if target == sum
157 end
158 end
159 results
160 end
161
162 def sum_subsets(numbers, target, partial=[], results = {})
163 sum = partial.inject(0, :+)
164 results[partial] = true if sum == target
165 return nil if sum > target
166
167 numbers.size.times do |n|
168 item = numbers[n]
169 remaining = numbers[(n + 1)..-1]
170 break if results.key?(remaining)
171 break if sum_subsets(remaining, target, partial + [item], results).nil?
172 end
173 results.keys
174 end
175
176<<-DOC
177 [1, 2, 3, 4, 5] t: 5
178 [[1, 4], [2, 3], [5]]
179
180 sum (j)
181 |0|1|2|3|4|5|
182 0|T|F|F|F|F|F|
183 1|T|T|F|F|F|F|
184 nums (i) 2|T|T|T|T|F|F|
185 3|T|T|T|T|T|T|
186 4|T|T|T|T|T|T|
187 5|T|T|T|T|T|T|
188
189dp[i][j] = dp[i-1][j] || dp[i-1][j - num[i-1]]
190
191dp[1][1] = dp[0][1] || dp[0][1]
192
193if [5][5] == true
194 then we have at least one possible solution
195 then we can backtrack from [5][5] up or right
196else
197 no solution
198DOC
199
200 #def sum_subsets(numbers, target)
201 #dp = Array.new(numbers.size + 1) { Array.new(numbers.size + 1, false) }
202 #dp[0][0] = true
203 #(numbers.size + 1).times do |i|
204 #(numbers.size + 1).times do |j|
205 #next if i == 0 && j == 0
206 #dp[i][j] = dp[i - 1][j] || dp[i - 1][j - numbers[i - 1]]
207
208 #end
209 #end
210 #PP.pp dp
211
212 #results = []
213 #i, j = 5, 5
214 ##loop do
215 ##if dp[i][j]
216 ##if j == target
217 ##results.push([sum])
218 ##i -= 1
219 ##else
220 ##target - j
221 ##end
222 ##end
223 ##end
224 #results
225 #end
226
227
228<<-DOC
229[2, 3, 7, 8, 10], t: 11
230[3, 8]
231
232 sum
233 |0|1|2|3|4|5|6|7|8|9|10|11|
2342 |T|F|T|F|F|F|F|F|F|F|F |F |
2353 |T|F|T|T|F|T|F|F|F|F|F |F |
2367 |T|F|T|T|F|T|F|T|F|T|T |F |
2378 |T|F|T|T|F|T|F|T|F|T|T |T |
23810|T|F|T|T|F|T|F|T|F|T|T |T |
239
240
241 sum (j)
242 |0|1|2|3|4|5|
243 (0) 1 |T|T|F|F|F|F|
244(i) (1) 2 |T|T|T|F|F|F|
245 (2) 3 |T|T|T|T|F|F|
246 (3) 4 |T|T|T|T|T|F|
247 (4) 5 |T|T|T|T|T|T|
248
249DOC
250
251 #def sum_subsets(numbers, target)
252 #dp = Array.new(numbers.size) { Array.new(numbers.size + 1, nil) }
253 #numbers.size.times { |n| dp[n][0] = true }
254
255 #(numbers.size).times do |i|
256 #number = numbers[i]
257 #0.upto(target) do |j|
258 #next if i == 0 && j == 0
259
260 #if number < j
261 #dp[i][j] = dp[i-1][j] || false
262 #else
263 #dp[i][j] = dp[i-1][j] || dp[i-1][j - number]
264 #end
265 #end
266 #end
267 #PP.pp dp
268 #i, j = numbers.size - 1, target
269 #results = []
270 #until i < 0 || j < 0
271 #puts [i, j, numbers[i], dp[i][j]].inspect
272 #if dp[i - 1][j]
273 #i -= 1
274 #else
275 #results << [j]
276 #j -= numbers[i]
277 #i -= 1
278 #end
279 #end
280 #results
281 #end
282
283 [
284 { arr: [1, 2, 3, 4, 5], num: 5, expected: [[1,4], [2,3], [5]] },
285 { arr: [1, 2, 2, 3, 4, 5], num: 5, expected: [[1,2,2], [1,4], [2,3], [5]] },
286 { arr: [], num: 0, expected: [[]] },
287 { arr: [1, 1, 1, 1, 1, 1, 1, 1, 1], num: 9, expected: [[1,1,1,1,1,1,1,1,1]] },
288 { arr: [1, 1, 2, 2, 2, 5, 5, 6, 8, 8], num: 9, expected: [[1,1,2,5], [1,2,6], [1,8], [2,2,5]] },
289 { arr: [1, 1, 2, 4, 4, 4, 7, 9, 9, 13, 13, 13, 15, 15, 16, 16, 16, 19, 19, 20], num: 36, expected: [[1,1,2,4,4,4,7,13], [1,1,2,4,4,4,20], [1,1,2,4,4,9,15], [1,1,2,4,9,19], [1,1,2,4,13,15], [1,1,2,7,9,16], [1,1,2,13,19], [1,1,2,16,16], [1,1,4,4,4,7,15], [1,1,4,4,4,9,13], [1,1,4,4,7,19], [1,1,4,4,13,13], [1,1,4,15,15], [1,1,9,9,16], [1,1,15,19], [1,2,4,4,7,9,9], [1,2,4,4,9,16], [1,2,4,7,9,13], [1,2,4,9,20], [1,2,4,13,16], [1,2,7,13,13], [1,2,9,9,15], [1,2,13,20], [1,4,4,4,7,16], [1,4,4,7,20], [1,4,7,9,15], [1,4,9,9,13], [1,4,15,16], [1,7,9,19], [1,7,13,15], [1,9,13,13], [1,15,20], [1,16,19], [2,4,4,4,7,15], [2,4,4,4,9,13], [2,4,4,7,19], [2,4,4,13,13], [2,4,15,15], [2,9,9,16], [2,15,19], [4,4,4,9,15], [4,4,9,19], [4,4,13,15], [4,7,9,16], [4,13,19], [4,16,16], [7,9,20], [7,13,16], [16,20]] },
290 { arr: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], num: 10, expected: [[1, 2, 3, 4], [1, 2, 7], [1, 3, 6], [1, 4, 5], [1, 9], [2, 3, 5], [2, 8], [3, 7], [4, 6], [10]] },
291 ].each do |x|
292 it do
293 result = sum_subsets(x[:arr], x[:num])
294 expect(result).to eql(x[:expected])
295 end
296 end
297end