Subsets I/II, Permutations I/II,Combinations I/II/III

Subset I
Given a collection of integers that might contain duplicates, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,2], a solution is:

[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]

public class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if (nums == null || nums.length == 0) return res;
        backtracking(nums, res, new ArrayList<Integer>(), 0);
        return res;
    }

    public void backtracking(int[] nums, List<List<Integer>> res, List<Integer> list, int curSize) {
        res.add(new ArrayList<Integer>(list));
        for (int i = curSize; i < nums.length; i++) {
            list.add(nums[i]);
            backtracking(nums, res, list, i+1);
            list.remove(list.size() - 1);
        }
    }
}

Subsets II, 可能有重复

public class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if (nums == null || nums.length == 0) return res;
        Arrays.sort(nums);
        backtracking(nums, new ArrayList<Integer>(), res, 0);
        return res;
    }

    public void backtracking(int[] nums, List<Integer> list,  List<List<Integer>> res, int start) {
        res.add(list);
        res.add(new ArrayList<Integer>(list));
        for (int i = start; i < nums.length; i++) {
            if (i != start && nums[i-1] == nums[i]) continue; // skip duplicates
            list.add(nums[i]);
            backtracking(nums, list, res, i + 1);
            list.remove(list.size() - 1);
        }
    }
}

46. Permutations

Given a collection of distinct numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

public class Solution {
public List<List> permute(int[] nums) {
List<List> res = new ArrayList<List>();
if (nums == null || nums.length == 0) return res;
helper(res, nums, new ArrayList());
return res;
}
public void helper (List<List> res, int[] nums, List list) {

    if (list.size() == nums.length) {
        if (!res.contains(list)) {
            res.add(new ArrayList(list));
        }
        return;
    }
    for (int i = 0; i &lt; nums.length; i++) {
        if (list.contains(nums[i])) continue;
        list.add(nums[i]);
        helper(res, nums, list);
        list.remove(list.size() - 1);
    }
}

}

<br />Permutation II, 可能出现重复元素

public class Solution {
public List<List> permuteUnique(int[] nums) {
List<List> res = new ArrayList<List>();
if (nums == null || nums.length == 0) return res;
Arrays.sort(nums);
int size = nums.length;
boolean[] used = new boolean[size];
backtracking(res, new ArrayList(), nums, used);
return res;
}

public void backtracking(List&lt;List&gt; res, List list, int[] nums, boolean[] used) {
    if (list.size() == nums.length) {
        res.add(new ArrayList(list));
        return;    
    }
    for (int i = 0; i &lt; nums.length; i++) {
        if (used[i] || (i != 0 &amp;&amp; !used[i - 1] &amp;&amp; nums[i - 1] == nums[i] )) continue;
        list.add(nums[i]);
        used[i] = true;
        backtracking(res, list, nums, used);
        list.remove(list.size() - 1);
        used[i] = false;
    }
}

}

<br />77. Combinations

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

For example,
If n = 4 and k = 2, a solution is:

[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

<br />解法: 

public class Solution {
public List<List> combine(int n, int k) {
List<List> res = new ArrayList();
if (n <= 0 || k n) return res;
int[] nums = new int[n];
for (int i = 0; i < nums.length; i++) {
nums[i] = i + 1;
}
backtracking(nums, new ArrayList(), res, 0, k);
return res;
}

public void backtracking(int[] nums, List list, List&lt;List&gt; res, int start, int k) {
    if (list.size() == k) {
        res.add(new ArrayList(list));
    }
    for (int i = start; i &lt; nums.length; i++) {
        list.add(nums[i]);
        backtracking(nums, list, res, i + 1, k);
        list.remove(list.size() - 1);
    }
}

}

<br />39. Combination Sum
Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:
All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.
For example, given candidate set [2, 3, 6, 7] and target 7, 
A solution set is: 
[
  [7],
  [2, 2, 3]
]

public class Solution {
public List<List> combinationSum(int[] candidates, int target) {
List<List> res = new ArrayList();
if (candidates == null || candidates.length == 0 || target < 0 ) return res;
Arrays.sort(candidates);
backtracking(candidates, target, res, new ArrayList(), 0);
return res;
}

public void backtracking(int[] candidates, int target, List&lt;List&gt; res, List list, int start) {
   if (target &lt; 0) return;    
   if (target == 0) {
       res.add(new ArrayList(list));
   }
   for (int i = start; i &lt; candidates.length; i++) {
       list.add(candidates[i]);
       backtracking(candidates, target - candidates[i], res, list, i);
       list.remove(list.size() - 1);
   }
}

}

<br />Combination Sum II
Each number in C may only be used once in the combination.


public class Solution {
public List<List> combinationSum2(int[] candidates, int target) {
List<List> res = new ArrayList();
if (candidates == null || candidates.length == 0 || target < 0) return res;
Arrays.sort(candidates);
backtracking(candidates, target, 0, res, new ArrayList());
return res;
}
public void backtracking(int[] candidates, int target, int start, List<List> res, List list) {
if (target < 0) return;
if (target == 0) {
res.add(new ArrayList(list));
return;
}
for (int i = start; i < candidates.length; i++ ) {
if (i != start && candidates[i] == candidates[i – 1]) continue;
list.add(candidates[i]);
backtracking(candidates, target – candidates[i], i + 1, res, list);
list.remove(list.size() – 1);
}
}
}

<br />216. Combination Sum III

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.


Example 1:

Input: k = 3, n = 7

Output:

[[1,2,4]]

Example 2:

Input: k = 3, n = 9

Output:

[[1,2,6], [1,3,5], [2,3,4]]

public class Solution {
public List<List> combinationSum3(int k, int n) {
List<List> res = new ArrayList();
if (k < 1 || n <= 0) return res;
backtracking(k, n, res, new ArrayList(), 1);
return res;
}

public void backtracking(int k, int target, List&lt;List&gt; res, List list, int start) {
    if (target &lt; 0) return;
    if (target == 0 &amp;&amp; list.size() == k) {
        res.add(new ArrayList(list));
        return;
    }
    for (int i = start; i &lt;= 9; i++) {
        list.add(i);
        backtracking(k, target - i, res, list, i + 1);
        list.remove(list.size() - 1);
    }
}

}
“`

Advertisements

93. Restore IP Addresses

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

For example:
Given “25525511135”,

return [“255.255.11.135”, “255.255.111.35”]. (Order does not matter)

思路: 有效的IP地址由4段构成,每段最多3位数,数字在[0,255]区间范围内。
首先我们要对输入做些基本的边界判断,例如s是否为null, 4<=s.length()<=12.
我们可以用一个临时list来盛放每段的ip地址,最后把list 转化为String加入到最终结果List里面;
递归结束条件: 满足保存ip地址的临时list.size() == 4的情况下: 1. 记录当前位置的pos正好为给定字符串s的长度,否的话,返回; 2. 满足以上两个条件,就是一个合理解,把临时list转化为String加到最终结果List里面;
递归条件:从i=pos开始,到i < s.length() && i < pos + 3进行遍历,这是因为每段ip最多为3位数字构成; 对于每次求得的当前ip segment = s.substring(i, pos + 1); 调用isValid判断是否是合理的ip segment, 合理的话,加入到临时list;递归调用执行i+1步求解, 最后别忘了list中去除最后一个元素。

复杂度:

public class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> res = new ArrayList<>();
        if (s == null || s.length() < 4 || s.length() > 12) return res;
        helper(res, s, 0, new ArrayList<String>());
        return res;
    }

    public void helper(List<String> res, String s, int pos, List<String> ipList) {
        if (ipList.size() == 4) {
            if (pos != s.length()) return;
            res.add(convertListToString(ipList));
            return;
        }

        for (int i = pos; i < s.length() && i < pos + 3; i++) {
            String ipSeg = s.substring(pos, i+1);
            if (isValid(ipSeg)) {
                ipList.add(ipSeg);
                helper(res, s, i + 1, ipList);
                ipList.remove(ipList.size() - 1);
            }
        }
    }

    private boolean isValid(String s) {
        if (s == null || s.length() == 0) return false;
        if (s.charAt(0) == '0') {
            return s.equals("0");
        }
        int num = Integer.parseInt(s);
        return num > 0 && num < 256;
    }

    private String convertListToString(List<String> list) {
        StringBuilder sb = new StringBuilder();
        for (String s: list) {
            sb.append(s);
            sb.append(".");
        }
        String ipAddress = sb.toString();
        return ipAddress.substring(0, ipAddress.length() - 1);
    }
}

Reference:
https://segmentfault.com/a/1190000006245389

http://www.cnblogs.com/yrbbest/p/4437164.html

22. Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

思路: 递归, 左括号个数用left表示, 右括号用right表示;
递归终止条件: left == n && right == n
递归过程: 先加入左括号, 条件为left right)

public class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        if (n <= 0) return res;
        helper("", res, 0, 0, n);
        return res;
    }

    public void helper(String tmp, List<String> res, int left, int right, int n) {
        if (left == n && right == n) {
            res.add(tmp);
            return;
        }
        if (left < n) {
            helper(tmp + "(", res, left + 1, right, n);
        }
        if (right < left) {
            helper(tmp + ")", res, left, right + 1, n);
        }
    }
}

Follow up: 缩进输出
借鉴解法: 替换 left== n && right == n

int level = 0;
for(int i = 0; i < tmp.length(); i++){
    if(tmp.charAt(i) == '{'){
        for(int k = 0; k < level; k++){
            System.out.print('\t');
        }
        System.out.println('{');
        level++;
    } else {
        level--;
        for(int k = 0; k < level; k++){
            System.out.print('\t');
        }
        System.out.println('}');
    }
}

79. Word Search

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

For example,
Given board =

[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

word = “ABCCED”, -> returns true,
word = “SEE”, -> returns true,
word = “ABCB”, -> returns false.

思路: Backtracking 的方法来解决这道题目。我们需要先从board中找到第一个字符出现的位置,然后从这个位置开始往上,下,左,右开始寻找;这里我们要借助一个dfs(x,y, index, board, word)的函数来寻找; 当index==word.length的时候就找到了对应的字符,返回true; 注意边界条件的check,x,y要保证在board内,或者当board[x][y]!=word.charAt(index)的时候都返回false。
复杂度: Time复杂度: 遍历整个m * n 的board的时间复杂度为m * n,对于每个点都会往上下左右来遍历寻找, k为word长度,大概要遍历4^k次,所以总的时间复杂度大概在mn4^k.
Space: 由于word长度为k,recursive space大概在O(k).

public class Solution {
    public boolean exist(char[][] board, String word) {
        if (board == null || board[0] == null || board.length == 0 || board[0].length == 0 || word == null) return false;
        // find the first char of word in board
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (word.charAt(0) == board[i][j]) {
                    if (dfs(i, j, 0, board, word )) {
                        return true;
                    }
                }

            }
        }
        return false;
    }

    public boolean dfs(int x, int y, int index, char[][] board, String word) {
        if (index == word.length()) {
            return true;
        }
        if (x < 0 || y < 0 || x >= board.length || y >= board[0].length || board[x][y] != word.charAt(index)) 
            return false;
        char tmp = board[x][y]; // save the point's value
        board[x][y] = '#'; // mark the point first
        boolean flag = dfs(x - 1, y, index + 1, board, word) ||
                       dfs(x, y - 1, index + 1, board, word) ||
                       dfs(x + 1, y, index + 1, board, word) ||
                       dfs(x, y + 1, index + 1, board, word);
        board[x][y] = tmp;
        return flag;
    }
}

46/47. Permutations I/II

Permutations I

Given a collection of distinct numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

思路: 典型的backtracking问题,在递归过程中,list中的元素不断变化,当list.size()等于nums.length的时候,这时候就是一个满足条件的排列组合,需要放入最终结果, 把结果加入最终res的时候要重新创建个新的list, res.add(new ArrayList(list));
复杂度: Time: O(n!), Space(n)

public class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if (nums == null || nums.length == 0) return res;
        helper(res, nums, new ArrayList<Integer>());
        return res;
    }
    public void helper (List<List<Integer>> res, int[] nums, List<Integer> list) {

        if (list.size() == nums.length) {
            if (!res.contains(list)) {
                res.add(new ArrayList<Integer>(list));
            }
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (list.contains(nums[i])) continue;
            list.add(nums[i]);
            helper(res, nums, list);
            list.remove(list.size() - 1);
        }
    }
}

Permutations II

题目中给定的数字可能是重复的。 先对给定的数组中的元素进行排序, 这样重复的元素就会相邻。当我们再递归把元素放入list的时候,我们要判断当前元素有没有被用过,而且还要判断当前元素与数组中下一个元素是否相同,如果相同的话就要往下找,找到不同的元素为止。作为下一个元素插入到list当中。
所以我们再每次循环的时候要判断该位是否访问过 或者 前一位没有访问过的话,前一位元素是否跟后一位相同,我们需要找到不同的元素。

public class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if (nums == null || nums.length == 0) return res;
        Arrays.sort(nums);
        int size = nums.length;
        boolean[] used = new boolean[size];
        backtracking(res, new ArrayList<Integer>(), nums, used);
        return res;
    }

    public void backtracking(List<List<Integer>> res, List<Integer> list, int[] nums, boolean[] used) {
        if (list.size() == nums.length) {
            res.add(new ArrayList<Integer>(list));
            return;    
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i] || (i != 0 && !used[i - 1] && nums[i - 1] == nums[i] )) continue;
            list.add(nums[i]);
            used[i] = true;
            backtracking(res, list, nums, used);
            list.remove(list.size() - 1);
            used[i] = false;
        }
    }
}