Share my Java Solution


  • 0
    T

    My solution is the following with a time complexity of O(n!). If anyone has a better solution please help me improve mine :) it took 640ms to run which is not good.

    public class Solution {
         public static List<List<Integer>> combinationSum2(int[] candidates, int target) {
            List<List<Integer>> finalList = new ArrayList<List<Integer>>();
            Arrays.sort(candidates);
    
            comb (candidates,0, target, finalList, new ArrayList<Integer>());
            return finalList;
        }
        
        public static void comb (int[] candidates,int num, int target, List<List<Integer>> finalList, ArrayList<Integer> array){
        	if(target==0){
        		if(!finalList.contains(array)){   // No repeat solutions
        			finalList.add(array);
        			return;
        		}
        	}
        	if(target<0){     // solutions not accurate
        		return;
        	}
        	
        	for(int i = num;i< candidates.length;i++){
        		if(candidates[num]>target){
        			continue;
        		}
        		ArrayList<Integer> newArray = (ArrayList<Integer>) array.clone();
        		newArray.add(candidates[i]);
        		if(i<=candidates.length){
        			comb(candidates,i+1,target-candidates[i],finalList,newArray);
        		}   //   recursion to check the rest of the list
        		
        	}
        	return;
        }
    }

Log in to reply
 

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