LeetCode - Algorithms - 77. Combinations

just run code of others.

Problem

77. Combinations

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

Java

Iterative Algorithm

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public List<List<Integer>> combine(int n, int k) {
		List<List<Integer>> combinations = new ArrayList<List<Integer>>();

		int[] combination = new int[k];
		for (int i = 0; i < k; i++) {
			combination[i] = i;
		}

		while (combination[k - 1] < n) {
			List<Integer> comblist = new ArrayList<Integer>();
			for(int i=0; i<combination.length; i++) {
				comblist.add(combination[i]+1);
			}
			combinations.add(comblist);
			int t = k - 1;
			while (t != 0 && combination[t] == n - k + t) {
				t--;
			}
			combination[t]++;
			for (int i = t + 1; i < k; i++) {
				combination[i] = combination[i - 1] + 1;
			}
		}

		return combinations;        
    }
}

Submission Detail

  • 27 / 27 test cases passed.
  • Runtime: 3 ms, faster than 88.15% of Java online submissions for Combinations.
  • Memory Usage: 39.7 MB, less than 80.43% of Java online submissions for Combinations.

ref