Monday, June 24, 2013

combination sum@leetcode

刷题必备书籍Cracking the Coding Interview: 150 Programming Questions and Solutions 

简历:The Google Resume: How to Prepare for a Career and Land a Job at Apple, Microsoft, Google, or any Top Tech Company
算法学习书籍:Introduction to Algorithms
编程珠玑:Programming Pearls (2nd Edition)
C++ 学习:The C++ Programming Language, 4th Edition
经典操作系统书籍,龙书:Operating System Concepts
创业:The Start-up of You: Adapt to the Future, Invest in Yourself, and Transform Your Career
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 (a1a2, � , 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] 
» Solve this problem

思路还是dynamic programming,用recursion做。和前面已经做过的一道题思路很像,只需要改一些细节,要注意这个元素本身可以重复使用,所以不需要设VISITED[],但是很可能会出现重复的COMBINATION,所以要先SORT ARRAY。


2 comments:

  1. 个人感觉:递归是没错,但这个类似求子集的算法更像是回溯法的变型 能请问为何要称为DP吗?

    ReplyDelete

Leetcode 316. Remove Duplicate Letters

 这道题表面问的是如何删除重复,实际在问如何从多个字符选取一个保留,从而让整个字符串按升序排列。那么策略就是对于高顺位的字符比如‘a',就要选靠前位置的保留,而低顺位字符如’z'则应该尽量选取靠后位置保留。 算法大概思路:每看到一个字符,我们要决定是否保留 1. ...