Question in below code. It wrongs why candidates = [1], target = 1


  • 0
    X
    public class Solution {
        public ArrayList<ArrayList<Integer>> combinationSum(int[] candidates, int target) {
            
           
            
            ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
            if (candidates.length == 0){
                return result;
            }
             Arrays.sort (candidates);
             ArrayList<Integer> re = new ArrayList<Integer>();
             dfs(candidates, target, result, re, 0);
            return result;
        }
        
        public void dfs(int[] candidates, int target, ArrayList<ArrayList<Integer>> result,
                                                               ArrayList<Integer> re, int i){
            // for each element in candidates, we can let the element appear many times as requirement.
            // so for each one, find the max number
            // since the output should be non-descending manner
            // so we just need to in general start from the bottom
            // recursion
            
            
            
            // add condition to come back if target becomes negative
            if(target<0){
                return;
            }else{
                if (target == 0){
                    result.add(re);
                    return;
                }else{
                    while(i<candidates.length && target-candidates[i]>=0){
                        re.add(candidates[i]);
                        
                        dfs(candidates, (target-candidates[i]), result,re,i);
                        i++;
                        int l = re.size();
                        re.remove(l-1);
                        
                    }
                }
                    
            }
        
        }
    }

  • 1
    L

    hi, you should replace the while cycle as follows:

    ArrayList<Integer> re_bak = new ArrayList<Integer>(re);
    re.add(candidates[i]);
    dfs(candidates, (target-candidates[i]), result,re,i);
    i++;
    re = new ArrayList<Integer>(re_bak );

    since when target==s, result.add(re); you can change the re .


Log in to reply
 

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