Subsets/Combination/Permutation
什么时候需要sort 什么时候需要index parameter
Sort: 提前Break
小技巧：可以把上次的结果传入参数 prev
重复元素的处理 ：sort然后结合visited array对结果判断 默认相同的元素之间存在位置关系
Difference between combination and permutation
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 /重复元素处理
每次copy长度为K的List O(k)一共有指数个组合 生成这些组合O(2^n) 所以一共的复杂度 O(K*2^n)
/** Skip the duplicated values **/
public class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
Arrays.sort(candidates);
helper(res,new ArrayList<Integer>(),target,0,candidates);
return res;
}
public void helper(List<List<Integer>> res,List<Integer> cur,int target,int start,int[] arr){
if(target == 0){
res.add(new ArrayList<Integer>(cur));
return;
}
if(target < 0 || start >= arr.length){
return;
}
//Iterate
for(int i = start;i < arr.length;i++){
if(i > start && arr[i-1] == arr[i])continue;
if(arr[i] > target)break;
cur.add(arr[i]);
helper(res,cur,target - arr[i],i+1,arr);
cur.remove(cur.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];
}
}
254. Factor Combinations
循环Same here, traverse through the possible candidate and compute the leftovers. Since we are adding element in sorted order no need to care about duplicate.
public class Solution {
// the factors are from [2,n) so we try divide each of them, if there is no left over, add to the list and then we continue until the result is 0 but the first version contains duplicate result such as <2,2,3>
//how to avoid that? --总结怎么在reccursion中去除重复
public List<List<Integer>> getFactors(int n) {
if(n==1){
return new ArrayList();
}
List<List<Integer>> result = new ArrayList();
helper(result,new ArrayList(),2,n);
return result;
}
public void helper(List<List<Integer>> result,List<Integer>list,int start,int n){
if(n <=1 ){
//排除只有一种的情况 比如元素本身
if(list.size() > 1 ) result.add(new ArrayList(list));
return;
}
//每一层递减 比如传入8,则下一次8的factor就要从2~7中找 然而实际上还可以再缩小范围
for(int i = start;i <= (int)Math.sqrt(n);i++){
if(n%i==0){
list.add(i);
helper(result,list,i,n/i);
list.remove(list.size()-1);
}
}
//还是要检查n,因为上面的循环只是到平方根
list.add(n);
helper(result,list,n,1);
list.remove(list.size()-1);
}
}
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;
}
}
}
}
247. Strobogrammatic Number II
又是一个让我们枚举出所有结果的题 还是通过两个坐标左右夹击 枚举出结果 用数组表示
字典 判断什么时候到达了中间的点(只能用1，0，8) 以及0不能作为数字的开头
public class Solution {
public List<String> findStrobogrammatic(int n) {
List<String> list = new ArrayList<>();
char[] num1 = {'0','1','8','6','9'};
char[] num2 = {'0','1','8','9','6'};
char[] number = new char[n];
dfs(list, number, num1, num2, 0);
return list;
}
private void dfs(List<String> list, char[] number, char[] num1, char[] num2, int index){
int left = index;
int right = number.length - index - 1;
if(left > right){
list.add(new String(number));
return;
}
// We can fill in 0,1,8 only
if(left == right){
for(int i = 0; i < 3; i++){
number[left] = num1[i];
dfs(list, number, num1, num2, index + 1);
}
} else {
for(int i = 0; i < num1.length; i++){
if(index == 0 && i == 0) continue;
number[left] = num1[i];
number[right] = num2[i];
dfs(list, number, num1, num2, index + 1);
}
}
}
还有一种写法 可以参考248的helper
248. Strobogrammatic Number III
让计算在给定的range里的strobogrammatic个数 利用247里的方法 枚举出所有在给定的数的
位数范围内的数 然后一一判断在边缘的数是否在范围之内 这是以一种很笨的方法了。。
public class Solution {
//0,1,6,8,9
//we could find the total number of items smaller than a number
public int strobogrammaticInRange(String low, String high) {
List<String> res = new ArrayList<String>();
int count = 0;
//产生在位数之间的
for(int i = low.length();i <= high.length();i++){
res.addAll(helper(i,i));
}
for(String s: res){
if((s.length() == low.length() && s.compareTo(low) < 0)||((s.length() == high.length() && s.compareTo(high)>0)))continue;
count++;
}
return count;
}
//特定位数的Strobogrammatic Number 以2为步长向里面循环
public List<String> helper(int idx,int n){
if(idx == 0)return new ArrayList<String>(Arrays.asList(""));
if(idx == 1)return new ArrayList<String>(Arrays.asList("1","0","8"));
List<String> sub = helper(idx - 2,n);
//when can we add 0 to the start and end, whenever we are not processing the last step
List<String> res = new ArrayList<String>();
for(int i = 0;i < sub.size();i++){
String cur = sub.get(i);
if(idx < n)res.add("0" + cur + "0");
res.add("1" + cur + "1");
res.add("8" + cur+ "8");
res.add("6" + cur+ "9");
res.add("9" + cur+ "6");
}
return res;
}
}