99% Concise Java BackTracking Solution


  • 0
    O
    public class Solution {
        public List<List<Integer>> combinationSum(int[] candidates, int target) {
            Arrays.sort(candidates);
            List<List<Integer>> ans = new ArrayList<List<Integer>>();
            List<Integer> path = new ArrayList<Integer>();
            search(candidates, target, 0, ans, path);
            return ans;
        }
        
        private void search(int[] c, int target, int pos, List<List<Integer>> ans, List<Integer> path) {
            if (target == 0) {
                ans.add(new ArrayList<Integer>(path)); //ans.add(path) is so not ok!
                return;
            }
    
            for (int i = pos; i < c.length && c[i] <= target; i++) {
                path.add(c[i]);
                search(c, target - c[i], i, ans, path);
                path.remove(path.size() - 1);
            }
        }
        
        
    }

Log in to reply
 

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