小米笔试第一题 求目标数是否可以用数组内数相加

你想要的原理：https://blog.csdn.net/zichen_ziqi/article/details/82184495

暴力求解法... bool miHomeGiftBag(vector < int > p, int M, int idx) {     if (M<0 || (idx<0 && M>0)) return false;     else if (M==0) return true;     else {         for (int i=idx;i>=0;--i) {             if (miHomeGiftBag(p, M-p[i], i-1)) return true;         }         return false;     } }

百度搜了一下 0.78

调了半天的输入输出格式，用自带的输入输出一直0，重新按照题目要求写了输入输出就过了。。。 def miHomeGiftBag(p, M): if M == 0: return 1 if M < 0: return 0 if len(p) == 0: return 0 return miHomeGiftBag(p[1:],M-p[0]) or miHomeGiftBag(p[1:],M) _p_cnt = int(input()) _p = list(map(int, input().split())) _M = int(input()) res = miHomeGiftBag(_p, _M) print(res)

AC 可以看一下,其实就是背包问题换一下就好了 #!/bin/python # -*- coding: utf8 -*- import sys import os import re #请完成下面这个函数，实现题目要求的功能 #当然，你也可以不按照下面这个模板来作答，完全按照自己的想法来 ^-^  #******************************开始写代码****************************** def  miHomeGiftBag(p, m):     dp = [0 for _ in range(m+1)]     for i in range(len(p)):         for j in range(m,0,-1):             if j >= p[i]:                 dp[j] = max(dp[j],dp[j-p[i]] + p[i])     return dp[-1]==m #******************************结束写代码****************************** N = int(input()) tmp = list(map(int,input().split())) M = int(input())    res=miHomeGiftBag(sorted(tmp), M) print(str(int(res)) + "\n")