Dropbox Intern OA 电面 两轮

写了个dp，但是加了个丑陋的去重，所以时间复杂度也不低

1. package dropbox;
   
2. 
   
3. 
   
4. import java.util.*;
   
5. 
   
6. public class Soda{
   
7. 
   
8.         public static void main(String[] args){
   
9.                 System.out.println(solve(new int[]{1,6,12}, 12));
   
10.         }
    
11. 
    
12.         private static List<List<Integer>> solve(int[] sizes, int total){
    
13.                 Map<Integer, List<List<Integer>>> hash = new HashMap<>();
    
14. 
    
15.                 for (int i = 0; i <= total; i++){
    
16.                         hash.put(i, new ArrayList<List<Integer>>());
    
17.                 }
    
18. 
    
19.                 for (int i = 1; i <= total; i++){
    
20.                         List<List<Integer>> container = hash.get(i);
    
21.                         for (int size : sizes){
    
22.                                 if (size <= i){
    
23.                                         if (hash.get(i - size).size() == 0){
    
24.                                                 List<Integer> temp = new ArrayList<>();
    
25.                                                 temp.add(size);
    
26.                                                 container.add(temp);
    
27.                                         }
    
28.                                         else{
    
29.                                                 for (List<Integer> list : hash.get(i - size)){
    
30.                                                         List<Integer> temp = new ArrayList<>();
    
31.                                                         temp.add(size);
    
32.                                                         temp.addAll(list);
    
33.                                                         if (!hasDup(container, temp)){
    
34.                                                                 container.add(temp);
    
35.                                                         }
    
36.                                                        
    
37.                                                         //System.out.println("i: " + i + " size: " + size);
    
38.                                                         //System.out.println("container: " + container);
    
39.                                                 }
    
40.                                         }
    
41.                                 }
    
42.                         }
    
43.                 }
    
44.                
    
45.                 //System.out.println(hash.get(total));
    
46.                
    
47.                 return hash.get(total);
    
48.         }
    
49.        
    
50.         private static boolean hasDup(List<List<Integer>> container, List<Integer> checker){
    
51.                 for (List<Integer> list : container){
    
52.                         if (list.containsAll(checker)) return true;
    
53.                 }
    
54.                
    
55.                 return false;
    
56.         }
    
57. }

复制代码

这题应该是lc里的combination sum 而不是 combination sum II 吧

seasean 发表于 2017-11-27 09:21
这题应该是lc里的combination sum 而不是 combination sum II 吧

对吧。combination sum 是可以用多次