Share my DP solution for java


  • 0
    R

    The basic idea is use array to store the list of i-1 for number i.
    The findIndex is used for sorting each list in case of the array given to us is not sorted.
    This solution is also useful for subsets|| if you change the

    list[i].add(n_list);
    
    
    
       to
    
    
    
    if(!list[i].contains(n_list)){
        			list[i].add(n_list);
      }
    

    If there is any question, feel free to comment.

    public List<List<Integer>> subsets(int[] S) {
            List<List<Integer>>[] list = new ArrayList[S.length+1];
            list[0] = new ArrayList<List<Integer>>();
            list[0].add(new ArrayList<Integer>());
            if(S.length==0){
            	return list[0];
            }
            for(int i=1;i<=S.length;i++){
            	list[i] = new ArrayList<List<Integer>>(list[i-1]); 
            	for(List<Integer> subList : list[i-1]){
            		List<Integer> n_list = new ArrayList<Integer>(subList);
            		n_list.add(findIndex(n_list, S[i-1]),S[i-1]);
            		list[i].add(n_list);
            	}
            }
            return list[S.length];
        }
        public int findIndex(List<Integer> list, int num){
        	int index = 0;
        	for(int i = 0;i<list.size();i++){
        		if(num>list.get(i)){
        			index = i+1;
        		}
        	}
        	return index;
        }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.