待字闺中面试题实现代码-数组求和

python

#!/usr/local/bin/python2.7
# encoding: utf-8
'''
FindSum -- There is an array with positive integer. given a positive integer S,\
 find the total number of combinations in Which the numbers' sum is S. 

FindSum is a description

It defines classes_and_methods

@author:     zhangzhi       
@deffield    updated: Updated
'''
import sys
import timeit
import cProfile

def find_sum_recursive(number_list, sum_to_find):
    count = 0
    
    for i in range(len(number_list)):        
        sub_sum = sum_to_find - number_list[i]
        if sub_sum < 0:
            continue
        elif sub_sum == 0:
            count += 1
            continue
        else:            
            sub_list = number_list[i + 1:]            
            count += find_sum_recursive(sub_list, sub_sum)       
    return count
 
def find_sum_DP(number_list, sum_to_find):
    count = [[0 for i in xrange(0, sum_to_find + 1)] for j in xrange(0, len(number_list) + 1)]    
    
    for i in range(len(number_list) + 1):
        for j in range(sum_to_find + 1):            
            if (0 == i and 0 == j):                
                count[i][j] = 1            
            elif (i > 0 and j > 0):                
                if (j > number_list[i - 1]):                    
                    count[i][j] = count[i - 1][j] + count[i - 1][j - number_list[i - 1]]
                elif(j < number_list[i - 1]):
                    count[i][j] = count[i - 1][j]
                else:
                    count[i][j] = count[i - 1][j] + 1                                
            else:                
                count[i][j] = 0
                
    return count[len(number_list)][sum_to_find]
   
def main(argv=None):  # IGNORE:C0111
    # number_list = [5, 5, 10, 3, 2, 9, 8, 7, 6, 4, 3, 2, 9, 5, 4, 7, 2, 8, 3]
    number_list = [5, 5, 10, 3, 2, 9, 8]
    sum_to_find = 15
    input_setup = ';number_list = [5, 5, 10, 3, 2, 9, 8, 7, 6, 4, 3, 2, 9, 5, 4, 7, 2, 8, 3];sum_to_find = 15'
        
    print 'Calculating...'
    print 'recursive starting'
    count = find_sum_recursive(number_list, sum_to_find)
    print timeit.timeit('count = find_sum_recursive(number_list, sum_to_find)', setup='from __main__ import find_sum_recursive' + input_setup, number=10)
    cProfile.run('find_sum_recursive(' + str(number_list) + ',' + str(sum_to_find) + ')')
    print 'recursive ended:', count    
    print 'DP starting'
    count_DP = find_sum_DP(number_list, sum_to_find)
    print timeit.timeit('count_DP = find_sum_DP(number_list, sum_to_find)', setup='from __main__ import find_sum_DP' + input_setup, number=10)
    cProfile.run('find_sum_DP(' + str(number_list) + ',' + str(sum_to_find) + ')')
    print 'DP ended:', count_DP        
    print 'Finished.'    

if __name__ == '__main__':
    sys.exit(main())

问题

一个数组只包含正整数。求出数组中和为S的任意组合