原题链接：https://www.nowcoder.com/questionTerminal/a5190a7c3ec045ce9273beebdfe029ee?toCommentId=390344
去年找工作时参加了网易的内推，编程题的确有难度，其中对于我来讲最难懂的一道题就是下面的那个“幸运的袋子”， 后来在参考 济南大学的 smallx 的C语言代码后将其翻译成python 代码， 并写此随笔作为记录。
这里给出 网友 smallx 给出的C语言代码：
1 #include <iostream> 2 #include <stdlib.h> 3 using namespace std; 4 5 int n; 6 int nums[1000]; 7 8 int cmp(const void * a, const void * b) { 9 return *(int*)a - *(int*)b; 10 } 11 12 // 思路：DFS生成全组合，同时注意剪枝、避免重复组合 13 int findall(int nums[], int index, long sum, long multi) { 14 int count = 0; 15 for(int i=index; i<n; i++) { 16 sum += nums[i]; 17 multi *= nums[i]; 18 if(sum > multi) 19 count += 1 + findall(nums, i+1, sum, multi); 20 else if(nums[i] == 1) 21 count += findall(nums, i+1, sum, multi); 22 else 23 break; 24 sum -= nums[i]; 25 multi /= nums[i]; 26 // 跳过相等的元素，避免重复组合 27 while(i<n-1 && nums[i]==nums[i+1]) 28 i++; 29 } 30 return count; 31 } 32 33 int main(int argc, char* argv[]) 34 { 35 while(cin >> n) { 36 for(int i=0; i<n; i++) 37 cin >> nums[i]; 38 39 // 从小到大排序 40 qsort(nums, n, sizeof(int), cmp); 41 cout << findall(nums, 0, 0, 1) << endl; 42 } 43 44 return 0; 45 }
根据以上代码进行 Python 重写的代码：
1 import sys 2 N=int(sys.stdin.readline()) 3 data=[int(k) for k in sys.stdin.readline().split()] 4 5 data.sort() 6 7 def findall(dindex, dsum, dmuti): 8 dcount=0 9 i=dindex 10 11 while(i<N): 12 dsum+=data[i] 13 dmuti*=data[i] 14 if(dsum>dmuti): 15 dcount=dcount+1+findall(i+1, dsum, dmuti) 16 elif(data[i]==1): 17 dcount=dcount+findall(i+1, dsum, dmuti) 18 else: 19 break 20 dsum=dsum-data[i] 21 dmuti=dmuti/data[i] 22 while(i<N-1 and data[i]==data[i+1]): 23 i=i+1 24 i=i+1 25 return dcount 26 27 print findall(0, 0, 1)
直观上感觉Python写的代码更加简单，但是实际上对于这种ACM类型的编程题使用PYTHON语言会变得十分别扭，因为Python语言对很多的基础操作的封装后对那内存的具体操作性变差，有可能用C语言很简单的一条语句就可以完成的事情用Python语言却难以做到，但是有弊必有利，python语言的高度封装性使它对于数据挖掘这一类的复杂算法十分的适应，虽然他降低了运算效率却提高了开发效率，简洁易懂。
总结：对于ACM一类的算法建议使用C语言，这样的话写起来会更加简洁易懂，思路也更加清晰。