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

本文首发于我的个人博客：Suixin's Blog

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

image
image

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

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

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

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)

测试：

> python3 mi.py
2
1 4
6
> 0

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

参考

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