小米笔试题「小米大礼包」Python代码

前几天一位朋友问我一道小米的笔试编程题,一看题目,这么简单?直接遍历list再用if判断不就行了。事实证明我还是too naive,写了几句便写不下去了……WTF……

话不多说,上题。


事实上,题目的本质为判断一个集合是否有子集之和等于一个固定的数字。可将问题分为两个子问题:

  1. 包含最后一个数字,循环其余N-1个数字判断是否等于M-set[n-1];
  2. 去掉最后一个数字,循环其余N-1个数字判断是否等于M

GeeksforGeeks上一位大牛利用递归的思想给出了解题思路,我将部分代码修改如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def miHomeGiftBag(n, set, sum):
# Base Cases
if (sum == 0):
return True
if (n == 0 and sum != 0):
return False

# If last element is greater than sum, then ignore it
if (set[n - 1] > sum):
return miHomeGiftBag(set, n - 1, sum)

'''
else, check if sum can be obtained by any of the following:
(a) including the last element
(b) excluding the last element
'''
return miHomeGiftBag(set, n - 1, sum) or miHomeGiftBag(set, n - 1, sum - set[n - 1])


# get parameters from terminal
N = int(input())
gift_money = list(map(int, input("").split()))
# print(gift_money)
M = int(input())

res = miHomeGiftBag(gift_money, N, M)
if res:
print(1)
else:
print(0)

测试:

1
2
3
4
5
> python3 mi.py
2
1 4
6
> 0

1
2
3
4
5
> python3 mi.py
4
2 3 8 1
5
> 1

参考

https://www.geeksforgeeks.org/subset-sum-problem-dp-25/