解题思路
cand[]={1,2,3,4} target=4;
相关代码
class Solution {List<List<Integer>> res;List<Integer> path;boolean st[];public List<List<Integer>> combinationSum2(int[] candidates, int target) {path = new ArrayList<>();res = new ArrayList<>();st = new boolean[candidates.length];Arrays.sort(candidates);dfs(path,0,candidates,0,target);return res;}public void dfs(List<Integer> path,int u,int candidates[],int sum,int target){if(sum>target){return;}if(sum==target){ Collections.sort(path);if(res.contains(new ArrayList<>(path))!=true)res.add(new ArrayList<>(path));return;}//u表示的是从第几个数开始搜索，如果搜索到了，把这个数放到搜索树中//i++的意思是保证path中存储的数是有序的for(int i=u;i<candidates.length;i++){if(st[i]==false){st[i]=true;path.add(candidates[i]);sum=sum+candidates[i];//i+1的意思是下一次搜索cand数组应该从下标为i+1开始。dfs(path,i+1,candidates,sum,target);sum = sum - path.get(path.size()-1);path.remove(path.size()-1);st[i] = false;}}}
}
