(Java) Standard backtracking solution


  • 0
    C

    Using the backtracking template from the book The Algorithm Design Manual to solve the problem.

    The code can be further simplified.

    public class Solution {
        private List<List<Integer>> result;
    
    	private void backtrack(int[] a, int j, int k, int n) {
    		if (j == k) {
    			List<Integer> intList = new ArrayList<Integer>();
    			for (int i = 1; i < a.length; i++) {
    				intList.add(a[i]);
    			}
    			result.add(intList);
    		} else {
    			j++;
    			
    			int[] inPerm = new int[n+1];
    			
    			for (int i = 1; i < j; i++) {
    				if (a[i] != 0) inPerm[a[i]] = 1; // mark as not a candidate
    			}
    			
    			for (int i = 1; i <= n; i++) {
    				if ((inPerm[i] != 1) && (i > a[j-1])) {
    					a[j] = i;
    					backtrack(a, j, k, n);
    				}
    			}
    		}
    	}    
    
        public List<List<Integer>> combine(int n, int k) {
    		int[] a = new int[k+1];
    		result = new ArrayList<List<Integer>>();
    		backtrack(a, 0, k, n);
    		return result;        
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.