👨💻个人主页: 才疏学浅的木子 🙇♂️ 本人也在学习阶段如若发现问题,请告知非常感谢 🙇♂️ 📒 本文来自专栏: 算法 🌈 算法类型:Hot100题 🌈 ❤️ 支持我:👍点赞 🌹收藏 🤟关注
解法一
递归+回溯
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<>();
List<Integer> list = new ArrayList<>();
dfs(candidates,target,res,list,0);
return res;
}
public void dfs(int [] candidates,int target,List<List<Integer>> res,List<Integer> list,int idx){
if(target < 0 || idx >= candidates.length) return;
if(target == 0){
res.add(new ArrayList<>(list));
return;
}
for(int i = idx;i < candidates.length;i++){
list.add(candidates[i]);
dfs(candidates,target-candidates[i],res,list,i);
list.remove(list.size()-1);
}
}
}
解法一
递归+回溯
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
List<Integer> list = new ArrayList<>();
int visited[] = new int[nums.length];
dfs(res,nums,list,visited);
return res;
}
public void dfs(List<List<Integer>> res,int [] nums,List<Integer> list,int [] visited){
if(list.size() == nums.length){
res.add(new ArrayList<>(list));
return;
}
for(int i = 0;i < nums.length;i++){
if(visited[i] == 0){
visited[i] = 1;
list.add(nums[i]);
dfs(res,nums,list,visited);
list.remove(list.size()-1);
visited[i] = 0;
}
}
}
}
解法一
递归+回溯
class Solution {
public List<String> generateParenthesis(int n) {
List<String> res = new ArrayList<>();
StringBuilder sb = new StringBuilder();
dfs(res,sb,n,0,0);
return res;
}
public void dfs(List<String> res,StringBuilder sb,int n,int open,int close){
if(sb.length() == n * 2){
res.add(sb.toString());
return;
}
if(open < n){
sb.append('(');
dfs(res,sb,n,open+1,close);
sb.deleteCharAt(sb.length()-1);
}
if(close < open){
sb.append(')');
dfs(res,sb,n,open,close+1);
sb.deleteCharAt(sb.length()-1);
}
}
}