脸家加面，似乎他家最近新题很多？

1.     public int getNumber_dfs_Duplicate(int[] nums, int k) {
   
2.         List<List<Integer>> res = new ArrayList<>();
   
3.         backtrack(nums, k, res, new ArrayList<Integer>(), new boolean[nums.length], 0, 0);
   
4.         return res.size();
   
5.     }
   
6. 
   
7.     private void backtrack (int[] nums, int k, List<List<Integer>> res, ArrayList<Integer> tmp, boolean[] used, int sum, int start) {
   
8.         if (tmp.size() > 0 && sum < k) {
   
9.             res.add(new ArrayList<>(tmp));
   
10.         }
    
11. 
    
12.         for (int i = start; i < nums.length; i++) {
    
13.             if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) {
    
14.                 continue;
    
15.             }
    
16. 
    
17.             tmp.add(nums[i]);
    
18.             used[i] = true;
    
19.             backtrack(nums, k, res, tmp, used, tmp.get(0) + nums[i], i + 1);
    
20.             used[i] = false;
    
21.             tmp.remove(tmp.size() - 1);
    
22.         }
    
23.     }
    
24. }

复制代码

请问各位大神第一题对应lc上哪些题？ 我刷题少勿喷

真淘蛮 发表于 2017-8-6 21:46
nums = { 1}, k = 2 呢, 30楼的code , 跑完是0?

1+1=2 not < 2
so ans = 0

跑跑的白日梦 发表于 2017-8-7 01:40
自己写的，比较直接的解法：

补充内容 (2017-8-6 09:42):

我也发现有重复的时候，需要进去一个一个backtracking核对答案个数

pomme2016 发表于 2017-8-7 07:40
1+1=2 not < 2
so ans = 0

ans = 0 不对啊, 1 < 2, ans 应该是1

发现没有一个人讲清楚为什么two pointer 和 取power这么可以行得通，我小黑板上画了一下，可能是这样子的：
为了直观我在楼主基础上加了一个数成为：
A = [2, 3, 4, 5, 7]  
K = 8

用two pointer方法在取power处打印，得到两个范围：
【2-5】=>8
【3-4】=>2
最后结果8+2=10

【2-5】和【3-4】这俩范围怎么得来的很简单不说，可是怎么得出的8和2的呢？
按照下面这样，左边界保持，右边的 x-1 个数找subset数量，所以就是pow(2, x-1), 解法中这个x-1刚好就是j-i
{ [2,3,4,5], [2,3,5], [2,4,5], [2,5], [2,3,4], [2,4], [2,3], [2] }
拆成=> [2] · {[3,4,5], [3,5], [4,5], [5], [3,4], [4], [3], []} （【3，4，5】这个集合的所有子集）

{ [3,4], [3] }
拆成=> [3] · { [4], [] } （【4】这个集合的所有子集）

# 是不是这样看着舒服多了。。。
# 我要是说错了请大家指正！

真淘蛮 发表于 2017-8-6 21:46
nums = { 1}, k = 2 呢, 30楼的code , 跑完是0?

1(Min) + 1(Max)  不小于2 啊， 所以是0， 有什么问题吗。。。empty subset 又没有元素，具体算不算1个面试官说了算呗。。

lixiaonin 发表于 2017-8-8 09:28
发现没有一个人讲清楚为什么two pointer 和 取power这么可以行得通，我小黑板上画了一下，可能是这样子的： ...

取power就是基本排列组合，每个元素出现不出现一共2个情况， n个元素就是2^n. 题目没说不允许重复，可以这么算。

即使不允许重复，答案也是排列组合算出来。（k1+1） * （k2+1） *....*（kn+1）, where kn is the count of each unique element from i+1 to j-1

没人考虑重复问题吗

pomme2016 发表于 2017-8-5 13:27
我自己想一开始用的DP，然后发现真的可以双指针呢。
感觉下面写的代码是对的，跑了几个test case

你这个没法处理重复元素，重复元素情况怎么办？谢谢