77.Combinations

77. Combinations

题目地址

https://leetcode.com/problems/combinations/

题目描述

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

Example:
Input: n = 4, k = 2
Output:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

代码

Approach #1 Backtracking

class Solution {
  public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> ans = new LinkedList();
    List<Integer> local = new LinkedList();
    backtrack(local, ans, 1, k, n);
    return ans;
  }

  private void backtrack(List<Integer> local, List<List<Integer>> ans, int start, int k, int n) {
    if (local.size() == k) {
        ans.add(new LinkedList(local));
        return; // essential
    }

    for (int i = start; i <= n; i++) {
      local.add(i);
      backtrack(local, ans, i + 1, k, n);
      local.remove(local.size() - 1);
    }
  }

}

Approach #2 Lexicographic (binary sorted) Combinations

class Solution {
  public List<List<Integer>> combine(int n, int k) {
    LinkedList<Integer> nums = new linkedList<Integer>();
    for (int i = 1; i < k + 1; i++) {
      nums.add(i);
    }
    nums.add(n + 1);

    List<List<Integer>> output = new ArrayList<List<Integer>>();
    int j = 0;
    while (j < k) {
      output.add(new LinkedList(nums.subList(0, k)));
      j = 0;
      while ((j < k) && (nums.get(j + 1) == nums.get(j) + 1)) {
        nums.set(j, j + 1);
        j++;
      }
      nums.set(j, nums.get(j) + 1);
    }

    return output;
  }
}

Approach #3

public class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (k > n || k < 0) {
            return result;
        }
        if (k == 0) {
            result.add(new ArrayList<Integer>());
            return result;
        }

        result = combine(n - 1, k - 1);
        for (List<Integer> list : result) {
            list.add(n);
        }
        result.addAll(combine(n - 1, k));
        return result;
    }
}

Other Way

Approach #1 Iterative

class Solution {
  Stack<Integer> stack = new Stack<Integer>();
  stack.push(0);
  int[] result = new int[4];
  String[] source = new String[] {"a", "b", "c", "d"};
  int k = 3;

  String[] nextCombination(String[] source, int k, Stack<Integer> stack, int[] result) {
    int n = source.length;
    while (k != 0 && stack.size() > 0) {
      int index = stack.size() - 1;
      int value = stack.pop();
      while (value < n) {
        result[index++] = value++;
        stack.push(value);
        if (index == k) {
          String[]combination = new String[k];
          for (int i = 0; i < k; i++) {
            combination[i] = source[result[i]];
          }
          return combination;
        }
      }
    }
    return new String[]{};
  }
}

Approach #2 Backtrack

List<String> words = new ArrayList<String>(Arrays.asList("a", "b", "c"));
LinkedList<String> tmp =  new LinkedList<String>();
List<List<String>> ans = new ArrayList();
dfs(ans, words, tmp);

public void dfs(List<List<String>> ans, List<String> words, LinkedList<String> tmp){
        if (tmp.size() == 2) {
            ans.add(new LinkedList<>(tmp));
            return;
        }
        for (String str : words) {
            if (!tmp.contains(str)) {
                tmp.add(str);
                dfs(ans, words, tmp);
                tmp.removeLast();
            }
        }
    }