My Solution In JAVA


  • 3
    R

    Generally speaking it is a DFS solution

    public class Solution {
        public List<List<Integer>> combinationSum2(int[] candidates, int target) {
            if (candidates==null||candidates.length==0) return Collections.emptyList();//Or throw exception();
    
            List<List<Integer>> results = new LinkedList<>();
    
            LinkedList<Integer> work = new LinkedList<>();
    
            Arrays.sort(candidates);
    
            for (int i=0,len=candidates.length;i<len;i++){
    
                if (i>0&&candidates[i]==candidates[i-1]) continue; //Avoid duplicates;
                combinationSumHelper(candidates,i,target,work,results);//DFS
            }
            return results;
        }
        //Use DFS
        private void combinationSumHelper(int[] candidates,int index, int target,LinkedList<Integer> work,List<List<Integer>> results){
            //Compare candidates[index] and target;
            //If equals, terminate the search,return result 
            //If candidates[index] > target, terminate the search, no result
            //Otherwise, study rest of elements.
            if (candidates[index]>target){
                return;
            }else if (candidates[index]==target){//Update the 
                work.addLast(candidates[index]);
                results.add(new ArrayList<Integer>(work));
                work.removeLast();
                return;
            }
            work.addLast(candidates[index]);
            for (int i=index+1,len=candidates.length;i<len;i++){
                if (i>index+1&&candidates[i]==candidates[i-1]) continue;//Avoid dulipcates
                if (candidates[i]<=target-candidates[index]){
                    combinationSumHelper(candidates,i,target-candidates[index],work,results);
                }
            }
            work.removeLast();
        }
    }

  • 0
    Q

    Your method is concise but elusive, could you please give more tips? Thank you so much.


  • 0
    R

    Hello qian2 I have updated my solution with a DFS one. This one is even more consice and clear.


  • 0
    Q

    Thank you, the recursive solution is pretty concise, my solution is recursive too, but I don't know how to solve it iteratively, can you do that?


  • 0
    R

    I can do it in a BFS way. It is less effecient. Let me modify my original solution tomorrow.


  • 2
    R
    public class Solution {
        	    public List<List<Integer>> combinationSum2(int[] num, int target) {
        	       	List<List<Integer>> path = new LinkedList<List<Integer>>();
        	       
        			if (num == null || num.length == 0){
        				return Collections.emptyList();
        			}
        			Arrays.sort(num);
        
        			Queue<List<Integer>> lists = new LinkedList<List<Integer>>();
        			Queue<Integer> diff = new LinkedList<Integer>();
        			List<Integer> list = new LinkedList<Integer>();
        
        			diff.add(target);
        			lists.add(list);
                    int gap,last;
                    //Make a graph by BFS
        			while (!diff.isEmpty()) {
        				gap = diff.poll();
        				//System.out.print(diff+" ");
        				list = lists.poll();
        				
        				last = (!list.isEmpty())?list.get(list.size()-1):-1;
        				
        				for (int i = last+1; i < num.length; i++) {
        					 if (i>0&&num[i-1]==num[i]&&i-1>last) continue;//Avoid duplicates and visited
        					 
        					if (gap>=(num[i]+num[i])) {//if gap>=num[i] && gap<=2*num[i], it is impossible to make the target
        						
        						diff.add(gap-num[i]);
        						
        						List<Integer> temp = new LinkedList<Integer>(list);
        						temp.add(i);
        						lists.add(temp);
        						
        					} else if (gap==num[i]){
        						list.add(i);
        						path.add(list);
        					}else
        						continue;
        				}
        			}
        			//Make the result
        			List<List<Integer>> res	= new LinkedList<List<Integer>>();
        			for (List<Integer> pre:path){
        				ArrayList<Integer> result= new ArrayList<Integer>();
        					for (Integer i:pre)
        						result.add(num[i]);
        				res.add(result);
        			}
        			return res; 
        	    }
        }

  • 0
    R

    @qian2, I have attached the BFS answer.


  • 0
    Q

    Thank you, you are so smart!


Log in to reply
 

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