[Leetcode][Python]39: Combination Sum
2024-10-13 10:44:08
# -*- coding: utf8 -*-
'''
__author__ = 'dabay.wang@gmail.com' 39: Combination Sum
https://oj.leetcode.com/problems/combination-sum/ Given a set of candidate numbers (C) and a target number (T),
find all unique combinations in C where the candidate numbers sums to T.
The same repeated number may be chosen from C unlimited number of times. Note:
All numbers (including target) will be positive integers.
Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
The solution set must not contain duplicate combinations.
For example, given candidate set 2,3,6,7 and target 7,
A solution set is:
[7]
[2, 2, 3] ===Comments by Dabay===
递归。
先把candidates排序。
遍历candidates,用index来记录目前的指针。
''' class Solution:
# @param candidates, a list of integers
# @param target, integer
# @return a list of lists of integers
def combinationSum(self, candidates, target):
def combinationSum2(candidates, target, index, res, res_list):
if target == 0:
res_list.append(list(res))
return
while index < len(candidates) and target >= candidates[index]:
res.append(candidates[index])
combinationSum2(candidates, target-candidates[index], index, res, res_list)
res.pop()
index += 1 res_list = []
candidates.sort()
combinationSum2(candidates, target, 0, [], res_list)
return res_list def main():
sol = Solution()
candidates = [1,2]
target = 4
print sol.combinationSum(candidates, target) if __name__ == "__main__":
import time
start = time.clock()
main()
print "%s sec" % (time.clock() - start)
最新文章
- 面试题:给定数组a,找到最大的j-i, 使a[j]>;a[i]
- Sql Server系列:数据控制语句
- 51nod1057(python2计算n!)
- HTML锁定Table中某一列
- JavaScript_1
- Hello Stacked Column Chart
- jsp(一) : servlet基础
- 练习2 B题 - 求绝对值
- asp.net mvc中匿名类dynamic
- volatile可见性的一些认识
- 对于错误“Refused to execute script from &#39;...&#39; because its MIME type (&#39;&#39;) is not executable, and strict MIME type checking is enabled.”的处理。
- 8、Preferences
- hive parition的使用,分dynamic和static两种
- Exchange-重建见证服务器和目录
- ABP框架连接Mysql数据库
- day6_自定义类型转换
- 将句子表示为向量(上):无监督句子表示学习(sentence embedding)
- css学习日记
- css 文字展示两行 其余的省略号显示
- 数据库——SQL数据定义
热门文章
- 自学nodejs系列
- 原生应用native、Web应用、混合应用hybrid:3者的优缺点解析
- Hadoop--Hadoop的机架感知
- C++模板类中使用静态成员变量(例如Singleton模式)
- Handler机制原理图、源码、使用!!!!!
- linux学习方法之六
- sharepoint 2010 使用自定义列表模版创建列表(2)
- 1 &; 167. Two Sum I &; II ( Input array is sorted )
- Web--->;>;>;Cookie与Session
- VS2012 黑色护眼主题