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);
        }
    }
}