Permutations: http://www.lintcode.com/en/problem/permutations/#

  • or use used[i] to record used elements, instead to list.contains(..)
  • O(n!)
public ArrayList<ArrayList<Integer>> permute(ArrayList<Integer> nums) {    
        ArrayList<ArrayList<Integer>> rst = new ArrayList<>();
        if (nums == null || nums.size() == 0) {
            return rst;
        }

        ArrayList<Integer> list = new ArrayList<>();
        helper(list, rst, nums);

        return rst;
    }

    private void helper(ArrayList<Integer> list, 
            ArrayList<ArrayList<Integer>> rst, ArrayList<Integer> nums) {

        if (list.size() == nums.size()) {
            rst.add(new ArrayList<>(list));
        }

        for (int i = 0; i < nums.size(); i++) {

            if (list.contains(nums.get(i))) {
                continue;
            }

            list.add(nums.get(i));
            helper(list, rst, nums);
            list.remove(list.size() - 1);
        }                
    }

public ArrayList<ArrayList<Integer>> permute(ArrayList<Integer> nums) {
        // write your code here
        ArrayList<ArrayList<Integer>> rst = new ArrayList<ArrayList<Integer>>();
        if(nums == null || nums.size() == 0) return rst;

        boolean[] used = new boolean[nums.size()];
        dfs(rst, new ArrayList<Integer>(), nums, used);

        return rst;
    }

    private void dfs(ArrayList<ArrayList<Integer>> rst, List<Integer> list,
                     ArrayList<Integer> nums, boolean[] used){
        if(list.size() == nums.size()){
            rst.add(new ArrayList<Integer>(list));
            return;
        }

        for(int i = 0; i < nums.size(); i++){
            if(used[i]) continue;
            list.add(nums.get(i));
            used[i] = true;

            dfs(rst, list, nums, used);

            used[i] = false;
            list.remove(list.size() - 1);
        }
    }

Permutations ii: http://www.lintcode.com/en/problem/permutations-ii/

  • visited[] to record the element visited. <=> list.contains(..)
  • continue 的两种情况：
    • 正在访问的 visited[i] == 1
    • 正在访问的 和 之前访问过的 值相同 
    public ArrayList<ArrayList<Integer>> permuteUnique(ArrayList<Integer> nums) {
        // write your code here
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();

        if (nums == null || nums.size() == 0) {
            return result;
        }

        Collections.sort(nums);
        List<Integer> list = new ArrayList<>();
        int[] visited = new int[nums.size()];
        helper(result, list, nums, visited);

        return result;

    }

    private void helper(ArrayList<ArrayList<Integer>> result, 
    List<Integer> list, ArrayList<Integer> nums,
    int[] visited) {

        if (list.size() == nums.size()) {
            result.add(new ArrayList<Integer>(list));
            return;
        }

        for (int i = 0; i < nums.size(); i++) {

            // 既要保证 1.跳过重复元素 2.跳过已存在元素
            //因为是前一个元素 所以 0表示访问完成 而非 未访问
             if (visited[i] == 1 || 
             (i != 0 && nums.get(i).equals(nums.get(i - 1)) 
             && visited[i - 1] == 0)){
                 continue;
             }

            visited[i] = 1;
            list.add(nums.get(i));
            helper(result, list, nums, visited);
            list.remove(list.size() - 1);
            visited[i] = 0;

        }        
    }

public ArrayList<ArrayList<Integer>> permuteUnique(ArrayList<Integer> nums){ 
        ArrayList<ArrayList<Integer>> rst = new ArrayList<ArrayList<Integer>>();
        if(nums == null || nums.size() == 0) return rst;

        boolean[] used = new boolean[nums.size()];
        Collections.sort(nums);
        dfs(rst, new ArrayList<Integer>(), nums, used);

        return rst;
    }

        private void dfs(ArrayList<ArrayList<Integer>> rst, List<Integer> list,
                     ArrayList<Integer> nums, boolean[] used){
        if(list.size() == nums.size()){
            rst.add(new ArrayList<Integer>(list));
            return;
        }

        for(int i = 0; i < nums.size(); i++){
            if(used[i]) continue;
            list.add(nums.get(i));
            used[i] = true;

            dfs(rst, list, nums, used);

            used[i] = false;
            list.remove(list.size() - 1);
            while(i + 1 < nums.size() && nums.get(i + 1) == nums.get(i)){
                i ++;
            }
        }
    }

Combinations: http://www.lintcode.com/en/problem/combinations/

  • prev 记录上一个位置. 因为non duplicate, so dfs(... i + 1)
  • 不回头地向前 用prev 记录位置
  • O(k * C(k, n))
    public List<List<Integer>> combine(int n, int k) {
        // write your code here
        List<List<Integer>> rst = new ArrayList<>();
        if (n == 0) return rst;

        List<Integer> list = new ArrayList<>();

        dfs(rst, list, n, k, 1);
        return rst;
    }

    private void dfs(List<List<Integer>> rst, List<Integer> list, int n, int k, int prev) {

        if (list.size() == k) {
            rst.add(new ArrayList<>(list));
            return;
        }

        for (int i = prev; i <= n; i++) {
            list.add(i);
            dfs(rst, list, n, k, i + 1);
            list.remove(list.size() - 1);
        }
    }

Subsets: http://www.lintcode.com/en/problem/subsets/

  • no need for return, since it will automatically end;
  • use prev to record position. non duplicate, so dfs(... i + 1)
  • notice: i + 1, not pos + 1
  • O(n*2^n)
    public ArrayList<ArrayList<Integer>> subsets(int[] nums) {

        ArrayList<ArrayList<Integer>> rst = new ArrayList<>();
        ArrayList<Integer> list = new ArrayList<>();

        if (nums == null || nums.length == 0) {
            // 注意 input 为 [] 时，output 为 [[]]
            rst.add(list);
            return rst;
        }

        Arrays.sort(nums);
        dfs(nums, rst, list, 0);
        return rst;
    }

    private void dfs(int[] nums, ArrayList<ArrayList<Integer>> rst, 
    ArrayList<Integer> list, int prev) {

        rst.add(new ArrayList<>(list));

        for (int i = prev; i < nums.length; i++) {

            list.add(nums[i]);
            dfs(nums, rst, list, i + 1);
            list.remove(list.size() - 1);
        }
    }

Subsets ii - with dup: https://leetcode.com/problems/subsets-ii/#/description

  • to get the next no-dup element: while(i + 1 < nums.length && nums[i] == nums[i + 1]) i++;
public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> rst = new ArrayList<>();

        Arrays.sort(nums);
        dfs(rst, new ArrayList<>(), nums, 0);
        return rst;
    }

    private void dfs(List<List<Integer>> rst, List<Integer> list, int[] nums, int start){
        rst.add(new ArrayList<Integer>(list));

        for(int i = start; i < nums.length; i++){
            list.add(nums[i]);
            dfs(rst, list, nums, i + 1);
            list.remove(list.size() - 1);
            while(i + 1 < nums.length && nums[i] == nums[i + 1]) i++;
        }
    }

Combination Sum: http://www.lintcode.com/en/problem/combination-sum/#

  • can use same elements. input may have dup.
  • prev 记录前一个位置. 因为可以 duplicate so i = prev cf. Combinations
  • 注意 input 自带duplicate 的 case e.g. [2, 2, 3], 在 for loop 中 filter 即可
  • Be aware: if (i != 0 && candidates[i] == candidates[i - 1]) { continue; }
    • not only skip dup in same level
    • but also skip dup in sub tree (which cause error in combination sum ii)
  • O(k * 2^n)
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        // write your code here
        List<List<Integer>> rst = new ArrayList<>();
        if (candidates == null || candidates.length == 0) return rst;

        List<Integer> list = new ArrayList<>();
        Arrays.sort(candidates);

        dfs(rst, list, candidates, target, 0);
        return rst;
    }

    private void dfs(List<List<Integer>> rst, List<Integer> list, int[] candidates, int target, int prev) {

            if (target < 0) return;

            if (target == 0) {
                rst.add(new ArrayList<>(list));
                return;
            }

            for (int i = prev; i < candidates.length; i++) {
                // e.g. [2, 2, 3], need to skip the second 2
                //if (i != 0 && candidates[i] == candidates[i - 1]) {
                //    continue;
                //}

                list.add(candidates[i]);
                dfs(rst, list, candidates, target - candidates[i], i);
                list.remove(list.size() - 1);

                while (i+1 < candidates.length && candidates[i] == candidates[i+1]) i++;
            }
        }

Combination Sum ii:

  • can not use same element, while input has dup
  • use while ( i + 1 < candidates.length && candidates[i + 1] == candidates[i]) i++; to skip dup in raw input
  • if (i != 0 && candidates[i] == candidates[i - 1]) { continue; } will skip both dup in input array and sub tree.
  • use dfs(... i + 1) cf dfs(...i) in Combination Sum i
public List<List<Integer>> combinationSum2(int[] candidates, int target) {

        List<List<Integer>> rst = new ArrayList<>();
        if (candidates == null || candidates.length == 0) return rst;

        List<Integer> list = new ArrayList<>();
        Arrays.sort(candidates);

        dfs(rst, list, candidates, target, 0);
        return rst;

}

private void dfs(List<List<Integer>> rst, List<Integer> list, int[] candidates, int target, int prev) {

        if (target < 0) return;

        if (target == 0) {
        rst.add(new ArrayList<>(list));
        return;
        }
        for (int i = prev; i < candidates.length; i++) {

        list.add(candidates[i]);
        dfs(rst, list, candidates, target - candidates[i], i + 1);
        list.remove(list.size() - 1);

        if (i != 0 && candidates[i] == candidates[i - 1]) { continue; }}
}

Combination Sum iii: https://leetcode.com/problems/combination-sum-iii/#/description

  • n, k. no dup in input. can be used only once.
  • similar to ii, but without dup
  • O(C(k, 9))
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> rst = new ArrayList<>();
        if (k == 0) {
            return rst;
        }

        List<Integer> list = new ArrayList<>();
        dfs(rst, list, k, n, 1);
        return rst;
    }

    private void dfs(List<List<Integer>> rst, List<Integer> list, int k, int n, int prev) {

        if (k == list.size() && n == 0) {
            rst.add(new ArrayList<>(list));
        }

        for (int i = prev; i <= 9; i++) {

            list.add(i);
            dfs(rst, list, k, n - i, i + 1);
            list.remove(list.size() - 1);
        }        
    }

Combination Sum IV: https://leetcode.com/problems/combination-sum-iv/#/description

  • input has no dup. can use elements multiple times. different sequence count as different
  • total solution count, instead of all possible solutions
  • so DP instead of DFS
  • memorized search
class Solution {
    public int combinationSum4(int[] nums, int target) {

        int[] dp = new int[target + 1];
        dp[0] = 1;

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

        return dp[target];
    }
}

results matching ""

    No results matching ""