

class Solution {List<List<Integer>> res=new ArrayList<>();List<Integer> li=new ArrayList<>();public List<List<Integer>> combinationSum(int[] candidates, int target) {solut(candidates,target,0,0);return res;}void solut(int[] candidates, int target,int index,int listSum){if(listSum==target){res.add(new ArrayList<>(li));return;}for(int i=index;i<candidates.length&&listSum<=target;i++){li.add(candidates[i]);listSum+=candidates[i];solut(candidates,target,i,listSum);listSum-=li.get(li.size()-1);li.remove(li.size()-1);}}
}
class Solution(object):def combinationSum(self, candidates, target):res=[]li=[]def solut(candidates,target,index,listSum):if listSum>target:returnif listSum==target:res.append(li[:])returnfor i in range(index,len(candidates)):li.append(candidates[i])listSum+=candidates[i]solut(candidates,target,i,listSum)listSum-=li.pop()solut(candidates,target,0,0)return res