Leetcode–Combination Sum

The Problem:

Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:

  • All numbers (including target) will be positive integers.
  • Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1a2 ≤ … ≤ ak).
  • The solution set must not contain duplicate combinations.

For example, given candidate set 2,3,6,7 and target 7,
A solution set is:
[7]
[2, 2, 3]

Notes:

  1. As we allow using each number repeatedly,  the problem can be looked as recursive that we are going through the same loop to look for a target (the original target, or it subtract the numbers added to the list).
  2. As we don’t allow duplicates in the final result, the array need to be sort first. The index of element we are looking at should be passed to next recursion call, and only examine the index after, so that an ascending order is enforced in result.

Java Solution

public class Solution {
    public List<List<Integer>> result;
    
    public List<List<Integer>> combinationSum(int[] candidates, int target) {

        result = new ArrayList<List<Integer>>();
        if(candidates== null || candidates.length==0)return result;
        Arrays.sort(candidates);
        
        findTarget(target, candidates, 0, new ArrayList<Integer>());
        return result;
    }
    
    public void findTarget(int tar, int[] candidates, int index, List<Integer> onelist){
        for(int i = index; i < candidates.length; i++){
            if(tar-candidates[i] == 0){
                List<Integer> temp = new ArrayList<Integer>(onelist);
                temp.add(candidates[i]);
                result.add(temp);
            }
            else if(tar - candidates[i] > 0){
                List<Integer> temp = new ArrayList<Integer>(onelist);
                temp.add(candidates[i]);
                findTarget(tar-candidates[i], candidates, i, temp);
            }
        }
    }
    
}
Advertisements

One thought on “Leetcode–Combination Sum

  1. Pingback: Leetcode–Combination Sum II | Linchi is coding

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s