Java BackTrack Solution


  • 0
    F
    int[] mins = { 1, 2, 4, 8, 16, 32 };
    int[] hours = { 1, 2, 4, 8 };
    List<String> res = new ArrayList<String>();
    
    public List<String> readBinaryWatch(int num) {
    	backTrack(num, 0, 0, 0, 0);
    	return res;
    }
    
    private void backTrack(int num, int hour, int min, int index, int count) {
    	if (count == num) {
    		if (min < 10)
    			res.add(hour + ":0" + min);
    		else {
    			res.add(hour + ":" + min);
    		}
    		return;
    	}
    	int len = hours.length + mins.length;
    	for (int i = index; i < len; i++) {
    		if (i < mins.length) {
    			if (min + mins[i] >= 60)
    				continue;
    			min += mins[i];
    			count++;
    
    		} else {
    			if (hour + hours[i - mins.length] > 11)
    				continue;
    			hour += hours[i - mins.length];
    			count++;
    		}
    		backTrack(num, hour, min, i + 1, count);
    		if (i < mins.length) {
    			min -= mins[i];
    			count--;
    		} else {
    			hour -= hours[i - mins.length];
    			count--;
    		}
    	}

Log in to reply
 

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