非死不可面筋

刚挂电话，感觉面挂了。

国人小哥，上来发现回音有点严重，请面试官讲慢点。寒暄了两三句上题（背景音太大其实没听太清楚）
感觉像combination sum II变体，给了一个target，和一堆升序排好的数字，找出所有能组成target的结果。
例如：nums = {1, 2, 3}, target = 5
输出：{{1, 1, 1, 1, 1}, {2, 3}...}//每个数可以重复取，结果不能重复，例如{2，3}在结果里，{3, 2}不能在结果里
这里要注意的是，输入可能重复。会{1, 1, 1, 1, 2,

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

e/smiley/QQ/em25.gif" smilieid="107" border="0" alt="" />



补充内容 (2017-5-25 08:04):
今天说过了，国人果然给力。虽然big o有点差，算法效率有点低，不过看在bug free的份上，来onsite吧。炒鸡感动

lc上有一篇关于此类题目的总结很好，都是backtracking
https://discuss.leetcode.com/topic/46159/a-general-approach-to-backtracking-questions-in-java-subsets-permutations-combination-sum-palindrome-partitioning

嘛，总体来说不难，就是一时脑残：

1. public List<List<Integer>> combinationSum2(int[] candidates, int target) {
   
2.                 List<List<Integer>> res = new ArrayList<>();
   
3.                 if (candidates == null || candidates.length == 0) {
   
4.                         return res;
   
5.                 }
   
6. 
   
7.                 ArrayList<Integer> tmp = new ArrayList<>();
   
8.                 dfsHelper(tmp, res, target, 0, candidates);
   
9. 
   
10.                 return res;
    
11.         }
    
12. 
    
13.         private void dfsHelper(ArrayList<Integer> tmp, List<List<Integer>> res, int target, int start, int[] candidates) {
    
14.                 if (target == 0) {
    
15.                         res.add(new ArrayList<>(tmp));
    
16.                         return;
    
17.                 }
    
18. 
    
19.                 for (int i = start; i < candidates.length; i++) {
    
20.                         if (i != start && candidates[i] == candidates[i - 1]) {
    
21.                                 continue;
    
22.                         }
    
23. 
    
24.                         if (candidates[i] > target) {
    
25.                                 break;
    
26.                         }
    
27. 
    
28.                         tmp.add(candidates[i]);
    
29.                         dfsHelper(tmp, res, target - candidates[i], i, candidates);
    
30.                         tmp.remove(tmp.size() - 1);
    
31.                 }
    
32.         }

复制代码

不一定挂的，楼主。国人一般都挺好，而且这个只是电话面试。

他问“target大小是m，数组长度是n” 可能说明他想要dp做法

这题复杂度挺麻烦的。我觉得应该是这样， recursive的话 2^n   n并不是数组长度，假设  1，2，3.      target = 5，  那么问题转化为   {1，1，1，1，1，2，2，3} 里面任选一个。n就是转化后的长度吧。

这个题不就是combination sum II 吗，只是给你升序sort好了。
怎么dp做？

dynamic programming啊

这题如果没见过的话，要一小时之内做出来是真不容易。而且还是电面。国人小哥有点狠。

什么dp，这不就是sort以后一个头指针，一个尾指针就好了嘛，在试下一个的时候跳过重复的数字，所以复杂度就是排序复杂度nlog(n)

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

ecneralc 发表于 2017-5-23 12:39
什么dp，这不就是sort以后一个头指针，一个尾指针就好了嘛，在试下一个的时候跳过重复的数字，所以复杂度就 ...

哦，看成2SUM了