*subsets-permutations-combination.java

https://leetcode.com/problems/subsets/discuss/27281/A-general-approach-to-backtracking-questions-in-Java-(Subsets-Permutations-Combination-Sum-Palindrome-Partitioning)
subsets



permutations




combination




    
    

combination.java

78. Subsets
https://leetcode.com/problems/subsets/
Given a set of distinct integers, nums, return all possible subsets (the power set).
Note: The solution set must not contain duplicate subsets.
Example:
Input: nums = [1,2,3]
Output:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]
//n*2^n
class Solution {
    void dfs(int[] nums, int st, List<Integer> tempList, List<List<Integer>> list){
        list.add(  new ArrayList<>(tempList) );
        
        for(int i=st; i<nums.length; i++){
            tempList.add( nums[i]);
            dfs(nums, i+1, tempList, list );
            tempList.remove( tempList.size()-1 );
        }
    }
    //n*2^n
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> list= new ArrayList<>();
        dfs(nums, 0, new ArrayList<>(), list);
        return list;
    }
}

90. Subsets II
https://leetcode.com/problems/subsets-ii/submissions/
Share
Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).
Note: The solution set must not contain duplicate subsets.
Example:
Input: [1,2,2]
Output:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

class Solution {
    void dfs(int[] nums, int st, List<Integer> tempList, List<List<Integer>> list){
        list.add(  new ArrayList<>(tempList) );
        for(int i=st; i<nums.length; i++){
            if(i>st && nums[i]==nums[i-1]) continue;
            tempList.add( nums[i]);
            dfs(nums, i+1, tempList, list );
            tempList.remove( tempList.size()-1 );
        }
    }
    
    //n*2^n    
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> list= new ArrayList<>();
        Arrays.sort(nums);
        dfs(nums, 0, new ArrayList<>(), list);
        return list;        
    }
}

permutations.java

46. Permutations
https://leetcode.com/problems/permutations/
Given a collection of distinct integers, return all possible permutations.
Example:
Input: [1,2,3]
Output:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

class Solution {
    void dfs(int[] nums, List<List<Integer>> list, List<Integer> tempList){
        if( nums.length==tempList.size()){
            list.add( new ArrayList<>(tempList));
            return;
        }
        
        for(int i=0; i<nums.length; i++){
            if( tempList.contains(nums[i]) ) continue;
            tempList.add( nums[i] );
            dfs(nums, list, tempList);
            tempList.remove( tempList.size()-1 );
        } 
    }
    //n!
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> list= new ArrayList<>();
        dfs( nums, list, new ArrayList<>() );
        return list;
    }
}

47. Permutations II
https://leetcode.com/problems/permutations-ii/submissions/
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
Example:
Input: [1,1,2]
Output:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

class Solution {
    void dfs(int[] nums, List<List<Integer>> list, List<Integer> tempList, boolean[] marked){
        if( nums.length==tempList.size()){
            list.add( new List<>(tempList));
            return;
        }
        
        for(int i=0; i<nums.length; i++){
            if( marked[i] || (i>0 && nums[i]==nums[i-1] && false==marked[i-1]) ) continue;
            marked[i]= true;
            tempList.add( nums[i] );
            dfs(nums, list, tempList, marked);
            marked[i]= false;
            tempList.remove( tempList.size()-1 );
        } 
    }
    //n!
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> list= new ArrayList<>();
        Arrays.sort(nums);
        dfs( nums, list, new ArrayList<>(), new boolean[nums.length] );
        return list;        
    }
}

subset.java

asd