For example,
If n = 4 and k = 2, a solution is:
[ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]
public class Solution { private List<List<Integer>> result; private int[] x; private int nN; private int nK; public List<List<Integer>> combine(int n, int k) { // Backtracking problem result = new LinkedList<>(); if (n<=0 || k<=0 || k>n) return result; nN = n; nK = k; x = new int[k]; for (int i = 1; i <= n-k+1; i++) { x[0] = i; backTracking(i, 1); } return result; } private void backTracking(int i, int cnt) // cnt -- counting times { if (cnt == nK) { List<Integer> ret = new LinkedList<>(); for (int num : x) ret.add(num); result.add(ret); } else { for (int j = i+1; j <= nN; j++) { x[cnt] = j; if (nN-(j+1) >= (nK-1)-(cnt+1)) // The left numbers is enough backTracking(j, cnt+1); } } } }
No comments:
Post a Comment