Subsets/Combination/Permutation

什么时候需要sort 什么时候需要index parameter

小技巧：可以把上次的结果传入参数 prev

重复元素的处理 ：sort然后结合visited array对结果判断 默认相同的元素之间存在位置关系

78. Subsets

public class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        Arrays.sort(nums);
        helper(res,new ArrayList(),0,nums);
        return res;
    }
    public void helper(List<List<Integer>> res,List<Integer> cur,int start,int[] nums){
        res.add(new ArrayList(cur));
        for(int i = start;i < nums.length;i++){
            cur.add(nums[i]);
            helper(res,cur,i+1,nums);
            cur.remove(cur.size()-1);
        }
    }
}

77. Combinations

Do not need to sort this time because the numbers are organized 1....n

public class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if(k > n) return res;
        combine(res,new ArrayList<Integer>(), 1, n, k);
        return res;
    }
    public void combine(List<List<Integer>> res,List<Integer>list, int start, int n,int k){
        if(list.size() == k){
            res.add(new ArrayList<Integer>(list));
            return;
        }
        for(int i = start; i <= n;i++){
            list.add(i);
            combine(res,list,i+1,n,k);
            list.remove(list.size()-1);
        }
    }
}

39. Combination Sum

重复的元素可以多选几次 所以下一次进入的index应该是不变的

public class Solution {
    //for every number in the array, add or not add
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
         Arrays.sort(candidates);
         List<List<Integer>> res = new ArrayList<List<Integer>>();
         sum(res,new ArrayList<Integer>(),candidates,target,0);
         return res;
    }
    public void sum(List<List<Integer>> res, List<Integer> list, int candidates[],int target,int start){
        if(target == 0){
            res.add(new LinkedList<Integer>(list));
            return;
        }
        if(target > 0){
            for(int i = start;i < candidates.length;i++){
                if(target < candidates[i]) return;
                list.add(candidates[i]);
                sum(res,list,candidates,target-candidates[i],i);
                list.remove(list.size()-1);
            }
        }
    }
}

40. Combination Sum II

每个元素选一次 index参数加1 /重复元素处理

public class Solution {

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        helper(res,new ArrayList<Integer>(),candidates,0,target);
        return res;
    }
    public void helper(List<List<Integer>> result,List<Integer> current,int[] arr,int start,int target){
        if(target == 0){
            result.add(new ArrayList<Integer>(current));
            return;
        }
        if(target < 0 || start >= arr.length) {
            return;
        }
        for(int i = start;i < arr.length;i++){
            //skip the element the same element
            if(i > start && arr[i] == arr[i-1])continue;  
            current.add(arr[i]);
            helper(result,current,arr,i+1,target-arr[i]);
            current.remove(current.size()-1);
        }
    }

}

377. Combination Sum IV

Return the number of ways.. reminds of Dynamic Programming! If using DFS directly here it would get TLE so need to use HashMap to record the internal result

public class Solution {
    public int combinationSum4(int[] nums, int target) {
        return dfs(nums, 0, target, new HashMap<Integer, Integer>());
    }

    private int dfs(int[] nums, int curSum, int target, HashMap<Integer, Integer> map){
        if(curSum > target) return 0;
        if(curSum == target) return 1;

        if(map.containsKey(curSum)) return map.get(curSum);

        int count = 0;
        for(int i = 0; i < nums.length; i++){
            count += dfs(nums, curSum + nums[i], target, map);
        }

        map.put(curSum, count);
        return count;
    }
}

Dynamic Programming:

Not the same as backpack problem, we are computing the number of ways instead of the max/min use the target value as the outer loop

public class Solution {
    public int combinationSum4(int[] nums, int target) {
        // dp[sum] = number of ways to get sum 
        int[] dp = new int[target + 1];

        // initialize, one way to get 0 sum with 0 coins
        dp[0] = 1;

        for(int j = 1; j <= target; j++){
            for(int i = 0; i < nums.length; i++){
                if(j - nums[i] >= 0) dp[j] += dp[j - nums[i]]; 
            }
        }

        return dp[target];
    }
}

46. Permutations

Not related to the order any more, do not pass the current index in the parameter, use a boolean array to record whether the number has been chosen(No duplicate)

public class Solution { //加了一个boolean
   public List<List<Integer>> permute(int[] num) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if(num.length == 0 || num == null) return res;

        boolean[] visited = new boolean[num.length];  
        helper(num,res,new ArrayList<Integer>(),visited);
        return res;
    }
    public void helper(int[] num, List<List<Integer>> res, ArrayList<Integer> item,boolean[] visited){
        if(item.size() == num.length){
            res.add(new ArrayList<Integer>(item));
        }

        for(int i = 0; i < num.length;i++){
            if(!visited[i]){
                item.add(num[i]);
                visited[i] = true;
                helper(num,res,item,visited);
                item.remove(item.size()-1);
                visited[i] = false;
            }
        }
    }
 }